[백준] 2225번 : 합분해

문제

 

---

풀이

 

이 문제를 풀기 위해선 2차원 dp배열을 사용해야 한다.

dp[i][j]를 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수라고 하자.

 

쉽게하기 위해 N=4, K=3이라고 하자.

	0	1	2	3	4
1	1	1	1	1	1
2	1
3	1

먼저 K=1인 경우 dp[1][j]=1일 것이다.

0부터 j까지의 정수 1개를 더해서 그 합이 j가 되는 경우의 수는 j 스스로를 사용하는 경우 1개 뿐이기 때문이다.

 

다음으로 N=0인 경우 dp[i][0]=1일 것이다.

몇개의 숫자를 사용한들 그 합이 0이 되기 위해선 0만을 i개 더하는 경우 1개 뿐이기 때문이다.

 

그렇다면 K=2, N=1인 경우를 보자.

0부터 1까지의 정수 2개를 더해서 그 합이 1이 되어야 한다.

 

그 합을 a+b+c+d+e...이런식으로 나타낸다고 치면 a에 올 수 있는 수는 0~1까지 이다.

a=0이라면 그 뒤 정수 1개를 더해 1을 만들어야 하므로 dp[1][1]을 참조하게 된다.

a=1이라면 그 뒤 정수 1개를 더해 0을 만들어야 하므로 dp[1][0]을 참조하게 된다.

 

즉, dp[2][1]=dp[1][0]+dp[1][1]이 되는 것이다.

	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3
3	1

마찬가지로 dp[2][2]=dp[1][0]+dp[1][1]+dp[1][2]이다.

이걸 정리하면

 

dp[i][j] = dp[i-1][0]+...+dp[i-1][j]가 된다.

근데 위 표를 잘 보면 한가지 눈치챌 수 있는 것이 있다.

 

파란색으로 표시한 dp[1][0]과 dp[1][1]의 합은 빨간색으로 표시한 dp[2][1]과 같다.

그니까 다시 말해 dp[i][j]에 대해 dp[i-1][0]+...+dp[i-1][j-1] = dp[i][j-1]이다.

 

그러므로 아까 식을 다시 정리하면

dp[i][j] = dp[i][j-1]+dp[i-1][j]가 된다는 것이다.

 

	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15

표를 다 채우면 이렇게 되고 마지막에 dp[K][N]인 15를 리턴하면 된다.

---

소스코드

 

#include <iostream>

using namespace std;

const int DIVISOR = 1000000000;
long long dp[201][201];

int dpSeparate(int N, int K) {
    for (int i = 0; i <= N; i++) //K=1일 때
        dp[1][i] = 1;
    for (int i = 2; i <= K; i++) {
        dp[i][0] = 1; //i개의 숫자로 0을 나타내는 방법은 0을 i개 사용하는 방법 1개뿐
        for (int j = 1; j <= N; j++) //dp[i][j-1]에 dp[i-1][0]+...+dp[i-1][j-1]이 있음
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % DIVISOR;
    }
    return dp[K][N];
}

int main() {
    int N, K;

    cin >> N >> K;
    cout << dpSeparate(N, K);
}