Diamond/Diamond V1 BOJ 1211 : 보일의 법칙 문제 링크 : https://www.acmicpc.net/problem/1211 BOJ 24970 처럼 내가 좋아하는 digit DP 문제. 자기곱 := (자신) * (자신의 각 자리 숫자의 곱) 으로 정의한다. 예를 들어 24 의 자기곱은 24 * 2 * 4 = 192 이다. 1018 미만의 두 수 A, B가 주어졌을 때, 자기곱이 A 이상 B 이하인 숫자의 개수를 출력하면 된다. 우선 나는 F(N) := 자기곱이 N 이하인 숫자의 개수로 정의했다. 그렇게 된다면 답은 F(B) - F(A-1) 이 될 것이다. 이제 F(N)을 구하는 방법만 생각하면 된다. 나는 백트랙킹을 했는데, Naive 하게 돌아봐도 시간초과가 나지 않기 때문이다. 물론 1 ~ N 까지의 자기곱을 다 구한다는 소리가 아니고, 수를 .. 2022. 8. 15. 이전 1 다음