[99클럽 코테스터디 24일차 TIL / 백준] 2225 - 합분해 (DP)
99클럽 코테스터디 24일차 TIL
KeyWord : DP
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
풀이
N과 K의 크기를 1부터 증가시키며 메모제이션 하여 해결할 수 있다.
dp[k+1][n+1]라는 배열을 선언한 후, dp[i][j]에 각 경우의 수를 저장해가는 식으로 진행하자.
문제에서 주어진 예제입력 6 4를 기준으로 dp 배열을 시각적으로 나타내보았다.
| K\N | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | ||||||
| 3 | 1 | ||||||
| 4 | 1 |
일단 초기 dp가 이렇게 만들어진다는 것까지는 쉽게 이해된다. N=0일 때는 K가 얼마가 되든 K개의 0을 더하는 경우의 수 1, K=1일 때는 자기자신 하나만 포함하는 경우의 수 1이 된다.
이제 나머지 빈칸을 어떻게 채울지 고민해야 한다.
수가 너무 작으면 이해하기 힘드므로 dp[3][2] 일 때를 생각해보자.
- 0 + 0 + 2
- 0 + 2 + 0
- 2 + 0 + 0
- 0 + 1 + 1
- 1 + 0 + 1
- 1 + 1 + 0
일단 dp[3][2]는 이렇게 6개의 경우의 수가 나온다. 하지만 우리는 여기서 규칙성을 찾아야 한다.
- 2개의 수를 사용하여 0을 만드는 경우의 수는 1이다.
dp[2][0] = 1- 여기에 2만 더하면 0 + 2가 되므로 2가 만들어진다.
- 2개의 수를 사용하여 1을 만드는 경우의 수는 2이다.
dp[2][1] = 2→0 + 1/0 + 1- 여기에 1을 더하면
1 + 1이 되므로 2가 만들어 진다.
- 2개의 수를 사용하여 2를 만드는 경우의 수는 2이다.
dp[2][2] = 3→0 + 2/1 + 1/2 + 0- 여기에 0을 더하면
2 + 0이 되므로 2가 만들어진다.
이렇게 만들어지는 모든 경우의 수를 더하면 6이 도출된다.
즉, dp[3][2] = dp[2][0] + dp[2][1] + dp[2][2] 이런 수식이 도출된다.
이 규칙성에 따라 식을 일반화 하면, dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]이 된다.
이제 이 식을 이용하여 dp 배열을 채워보자.
| K\N | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
| 4 | 1 | 4 | 10 | 20 | 35 | 56 | 84 |
해를 구했다. 당연히 dp[4][6]에 저장된 84가 문제의 해다.
이렇게만 해도 코드를 구현할 수는 있겠지만, 뭔가 계산량을 더 줄일 수 있을 것 같다. 이 상태로 구현을 한다면 3중 반복문을 사용해야 한다. 2중 반복만 되어도 불편한데, 3중이라니?
조금 더 규칙성을 찾아보자.
dp[3][2] = dp[2][0] + dp[2][1] + dp[2][2]
이 수식을 자세히 살펴보면, dp[2][0] + dp[2][1] = dp[3][1] 이라는 사실을 알 수 있다.
식을 더 정리하면, dp[3][2] = dp[3][1] + dp[2][2]이다. 이를 일반화 하면, dp[i][j] = dp[i-1][j] + dp[i][j-1]이 된다.
이제 진짜 코드로 구현하자.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
int n = Integer.parseInt(stk.nextToken());
int k = Integer.parseInt(stk.nextToken());
int[][] dp = new int[k + 1][n+1];
Arrays.fill(dp[1], 1);
for (int i = 0; i < k + 1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
}
}
System.out.println(dp[k][n]);
}
}