📌 Problem
N과 K가 주어졌을 때 0부터 N까지의 숫자를 중복으로 K개 조합하여 N을 만들 수 있는 경우의 수를 구하면 된다. 이 때 조합의 구성이 같더라도 순서가 다르면 다른 경우이다. 예를 들어 (0, 1, 2)와 (1, 0, 2)는 합산값이 3으로 동일하지만 순서가 다르기 때문에 다른 경우이다.
📌 Solution
DP 문제는 규칙을 찾으면 되는데 이는 직접 하나씩 해보면 된다. 예제 입력 2번의 입력을 바탕으로 직접 적어보자. 예제 2번의 N은 6 K는 4이다. 이를 표로 나타내면 다음과 같다.
1개의 숫자만을 이용해서 각각의 숫자를 만드는 방법은 자기자신 하나 뿐이다.
2개의 숫자를 이용해서 각각의 숫자를 만드는 방법은 다음과 같다.
0 = (0, 0)
1 = (0, 1) (1, 0)
2 = (0, 2) (2, 0) (1, 1)
3 = (0, 3) (3, 0) (1, 2) (2, 1)
4 = (0, 4) (4, 0) (1, 3) (3, 1) (2, 2)
5 = (0, 5) (5, 0) (1, 4) (4, 1) (2, 3) (3, 2)
6 = (0, 6) (6, 0) (1, 5) (5, 1) (2, 4) (4, 2) (3, 3)
3개의 숫자를 이용해서 각각의 숫자를 만드는 방법은 다음과 같다.
0 = (0, 0, 0) = 1
1 = (0, 0, 1) x 3 = 3
2 = (0, 0, 2) x 3 + (0, 1, 1) x 3 = 6
3 = (0, 0, 3) x 3 + (0, 1, 2) x 6 + (1, 1, 1) = 10
4 = (0, 0, 4) x 3 + (0, 1, 3) x 6 + (0, 2, 2) x 3 + (1, 1, 2) x 3 = 15
5 = (0, 0, 5) x 3 + (0, 1, 4) x 6 + (0, 2, 3) x 6 + (1, 1, 3) x 3 + (1, 2, 2) x 3 = 21
6 = (0, 0, 6) x 3 + (0, 1, 5) x 6 + (0, 2, 4) x 6 + (0, 3, 3) x 3 + (1, 1, 4) x 3 + (1, 2, 3) x 6 + (2, 2, 2) = 28
4개의 숫자를 이용해서 각각의 숫자를 만드는 방법은 다음과 같다.
0 = (0, 0, 0, 0) = 1
1 = (0, 0, 0, 1) x 4 = 4
2 = (0, 0, 0, 2) x 4 + (0, 0, 1, 1) x 6 = 10
3 = (0, 0, 0, 3) x 4 + (0, 0, 1, 2) x 12 + (0, 1, 1, 1) x 4 = 20
4 = (0, 0, 0, 4) x 4 + (0, 0, 1, 3) x 12 + (0, 0, 2, 2) x 6 + (0, 1, 1, 2) x 12 + (1, 1, 1, 1) = 35
5 = (0, 0, 0, 5) x 4 + (0, 0, 1, 4) x 12 + (0, 0, 2, 3) x 12 + (0, 1, 1, 3) x 12 + (0, 1, 2, 2) x 12 + (1, 1, 1, 2) x 4 = 56
6 = (0, 0, 0, 6) x 4 + (0, 0, 1, 5) x 12 + (0, 0, 2, 4) x 12 + (0, 0, 3, 3) x 6 + (0, 1, 1, 4) x 12 + (0, 1, 2, 3) x 24 + (0, 2, 2, 2) x 4 + (1, 1, 1, 3) x 4 + (1, 1, 2, 2) x 6 = 84
그래프를 보면 1행과 1열을 제외하고 나머지는 dp[row][col] = dp[row -1][col] + dp[row][col - 1]이라는 것을 알 수 있다. 메모리 공간을 줄인다고 했을 때 dp[i] += dp[i - 1]이라는 것을 알 수 있다. 각각의 연산에 대해 나머지 연산을 하기 때문에 점화식은 dp[i] = (dp[i] + dp[i - 1]) % 1,000,000,000으로 세울 수 있다.
📌 Code
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int K = Integer.parseInt(tokenizer.nextToken());
int[] dp = new int[N + 1];
Arrays.fill(dp, 1);
while (K-- > 1) for (int i = 1; i <= N; i++) dp[i] = (dp[i] + dp[i - 1]) % 1_000_000_000;
result.append(dp[N]);