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 까지의 자기곱을 다 구한다는 소리가 아니고, 수를 구성하는 숫자들의 조합으로 백트랙킹했다.
제일 긴 17자리를 생각해봐도, 숫자조합은 얼마 되지 않는다.
1~9 의 숫자 중 17개를 중복을 허용하여 뽑는 가짓수는 9H17 = 25C17 = 25C8 = 1081575 가지에 불과하다.
17자리의 모든 조합을 다 고려해도 100만 남짓이기 때문에 시간초과가 날 일은 없다.
이제 특정 조합이 정해졌을 때 답을 빠르게 구하면 된다.
조합이 정해지면 (각 자리 숫자의 곱) 이 정해지므로, 우리는 N 에서 이 (각 자리 숫자의 곱) 을 나누고 시작한다.
N 에서 (각 자리 숫자의 곱) 을 나눈 수를 n 이라고 하자.
그러면 이 조합의 숫자들을 적절히 배열하여 n 이하로 만드는 가짓수만 찾으면 된다.
맨 앞자리부터 보면서 동자순열을 더해주면 된다. 예시로 살펴보면,
1. 숫자 조합이 1, 1, 1, 3, 3, 7 이고 n = 3705 라면
숫자 조합은 6자리인데 n은 4자리이므로 어떻게 해도 n 이하로 만들 수 없다. ∴ F(N) += 0
2. 숫자 조합이 1, 1, 1, 3, 3, 7 이고 n = 1048580 라면
숫자 조합은 6자리인데 n은 7자리이므로 무조건 n 이하로 만들 수 있다.
그냥 이 6개의 수를 나열하는 동자순열을 계산하면 6! / (3! 2! 1!) = 60 가지다. ∴ F(N) += 60
3. 숫자 조합이 1, 1, 1, 3, 3, 7 이고 n = 375000 라면
맨 앞이 1 이면 무조건 가능하고 나머지 5개 수 배열 방법은 5! / (2! 2!) = 30 가지다. ∴ F(N) += 30
다음으로는 맨 앞에 3을 박아줄 수 밖에 없다.
2번째 숫자가 1 이면 무조건 가능하고 나머지 4개 수 배열은 4! / 2! = 12 가지다. ∴ F(N) += 12
2번째 숫자가 3 이면 무조건 가능하고 나머지 4개 수 배열은 4! / 3! = 4 가지다. ∴ F(N) += 4
다음으로는 2번째 숫자에 7을 박아줄 수 밖에 없다.
3번째 숫자가 1이면 무조건 가능하고 나머지 3개 수 배열은 3! / 2! = 3가지다. ∴ F(N) += 3
3번째 숫자가 3이면 무조건 가능하고 나머지 3개 수 배열은 3! / 3! = 1가지다. ∴ F(N) += 1
다음으로는 더 이상 없다. 5는 3보다 크기 때문이다.
이런식으로 계산해주면 각 조합마다 O(자리 수) 정도로 구할 수 있다.