| 시간 제한 | 메모리 제한 |
| 2초 | 512MB |
문제
성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다.
- 배열의 길이는 N이다.
- 배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.
- 배열에서 연속한 수가 A와 B일 때, A <= B 또는 A % B != 0 을 만족해야 한다.
예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 <= 7, 7 <= 7, 7 % 2 != 0 조건을 만족하기 때문이다.
N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000)
출력
첫째 줄에 성관이가 좋아하는 배열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.
풀이
성관이가 좋아하는 배열의 세 번째 조건을 그대로 사용하지 않고 부정을 취하는 것이 이 문제의 출발점인 것 같다. "!A 또는 !B"의 부정은 "A 그리고 B"이다. 그래서 "A <= B 또는 A % B != 0" 전체를 부정하면 "A > B 그리고 A % B = 0"이 된다. 그럼 이 조건을 만족하는 A는 B보다 큰 B의 배수가 된다. 이렇게 만들어진 조건을 잘 활용하려면 배열을 구성하는 순서를 어떻게 해야할 까.
1. n자리에 올 수 "없는" 숫자를 찾는 방법
앞에서부터 배열을 만들어간다고 생각해보자. N = 3, K = 10인 경우를 가정해보면, 먼저 맨 앞자리에 올 수 있는 숫자는 1~10 전부다. 그 다음, 6이 맨 앞에 온 경우를 살펴보면 두 번째에 올 수 "없는" 수는 6보다 작으면서 6을 배수로 하는 1, 2, 3이다. 그럼 10가지 수 중에서 3가지 경우가 빠진 7가지 경우가 가능한 것이다. 10이 배치된 경우, 다음 숫자는 1, 2, 5를 제외한 7개의 수가 올 수 있다. 그럼 이렇게 배치될 수 없는 수를 찾을 수 있는 방법은 for문을 사용해 1부터 N까지의 수로 배열의 마지막에 있는 수를 나눠보는 것이다. 여기서 K//2까지만 나눠보면 되기 때문에 어느정도의 시간 절약은 가능하다. 하지만 K가지 숫자에 대해 K//2번의 나눗셈을 계속 해야하므로 시간복잡도는 O(K2)다.
거꾸로 배열을 만들어간다고 생각해보자. 역시 마찬가지 N = 3, K = 10인 경우를 살펴보면 맨 뒤에 올 수 있는 숫자는 10가지다. 맨 뒤가 3인 경우, 그 앞에 올 수 "없는" 숫자는 3보다 큰 3의 배수인 6, 9이다. 4의 경우는 8이 올 수 없다. 이 방법은 마찬가지 for문으로 탐색할 수 있다. 하지만 앞에서부터 배열을 만들어가는 경우는 for문의 스텝이 1이었으나 이 경우는 배수만 빠르게 찾을 수 있기 때문에 스텝을 넓혀서 탐색 시간을 줄일 수 있다. 시간복잡도는 O(KlogK)가 된다.
이 문제는 앞에서부터 배열을 만들어가면 시간초과가 뜨는 문제다..! (소름)
2. 배열의 가짓수를 관리할 방법
배열을 거꾸로 구성하는 방법에 따라 맨 뒷자리에는 K가지의 숫자가 모두 올 수 있다. 그 앞 자리에는 뒷 자리의 배수가 아닌 수들이 올 수 있다. 이 때, '각 자리 숫자의 다음 숫자가 무엇이냐'에 집중하면 가짓수를 관리할 때 숫자를 하나하나 이어붙여가면 bfs나 dfs로 관리해야 한다. 이렇게 되면 N과 K가 충분히 커졌을 때 512MB 제한을 가볍게 뛰어 넘는 양의 큐를 관리하거나 2초가 아니라 2시간 동안 재귀 호출과 탈출을 반복해야 한다. 따라서 가짓수의 관리는 '현재까지 마지막에 온 숫자가 무엇이냐'에 중점을 두고 다음과 같은 배열로 관리한다.
dp[i][j] = i자리 수의 배열 맨 앞 숫자가 j인 배열의 가짓수
그럼 1 <= j <= K 범위의 j에 대해 dp[i-1][j] 중에서 dp[i][k]를 구성하면 k가 j의 배수가 아닌 경우 dp[i][k] += dp[i-1][j]를 해줄 수 있다. 하지만! 여기서 j를 하나하나 키워가면서 k가 j의 배수인지 아닌지를 판별한다면 다시 시간복잡도가 O(K2)로 증가하게 된다. 그래서 새로운 배열 하나를 더 관리한다. 이 배열은 i자리 배열을 만들면서 i자리 배열의 모든 가짓수를 더해놓을 배열이다.
sum[i] = i자리 수의 배열을 만들 수 있는 모든 방법의 수
dp[i-1][j]를 이용해 dp[i][k]를 구성할 때, j보다 큰 j의 배수 j*t에 대해 dp[i][k] = sum[i-1] - ∑dp[i-1][j*t] 로 얻을 수 있다.(수식 표현 능력의 한계로 대충 썼는데 범위 안의 모든 j의 배수들을 빼겠다는 말이다.) 이렇게 하면 j의 배수들만 빼주면 되기 때문에 불필요한 덧셈 연산의 반복을 피할 수 있다. 점화식을 다시 정리하면 이렇다.
dp[i][k] = sum[i-1]
for t in range(j*2, K+1, j): dp[i][k] -= dp[i-1][t]
누적합을 구하다 보면 숫자가 매우 커진다. 큰 수의 연산은 횟수가 같더라도 작은 수의 연산보다 더 오랜 시간이 걸리기 때문에 dp[i][k]를 구할 때마다 1,000,000,007로 나누어주면 된다. 마지막엔 sum(N)이 N자리의 모든 배열의 가짓수를 나타내게 된다.
정답 코드
N,K = map(int,input().split())
div = int(1e9+7)
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
sum = [0 for _ in range(N+1)]
for i in range(1,K+1): dp[1][i] = 1
sum[1] = K
for i in range(2, N+1):
for j in range(1, K+1):
dp[i][j] += sum[i-1]
for k in range(j*2,K+1, j):
dp[i][j] -= dp[i-1][k]
sum[i] += dp[i][j]
sum[i] %= div
print(sum[N]%div)
