[백준 2225번 C++] 합분해

2225번: 합분해 (acmicpc.net)

2225번: 합분해

---

 

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

[이해하기]

N / K	1	2	3	4
1	1	2	3	4
2	1	3	6
3	1	4
4	1

K=1인 경우: 1가지씩

 

N=1, K=2인 경우: 0, 1 => 2가지

N=1, K=3인 경우: 0, 0, 1 => 3가지

N=1, K=4인 경우: 0, 0, 0, 4 => 4가지

 

N=2, K=2인 경우: 0, 2 / 1, 1 => 3가지

N=2, K=3인 경우: 0, 0, 2 / 0, 1, 1 => 6가지

 

N=3, K=2인 경우: 0, 3 / 1, 2 => 4가지

 

여기까지 하니까 규칙이 보인다!

점화식으로 나타내면 

d[i][j] = d[i-1][j] + d[i][j-1]

 

[참고]

[C++] 백준 2225 - 합분해 (tistory.com)

[C++] 백준 2225 - 합분해

---

#include <iostream>

using namespace std;

int main(){
    int d[201][201];
    int n, k;
    
    cin >> n >> k;
    
    //N=1인 경우 입력
    for (int i=0;i<=k;i++)
        d[1][i] = i;
    
    //N=2인 경우 입력
    for (int i=2;i<=n;i++)
        for (int j=1;j<=k;j++)
            d[i][j] = (d[i-1][j] + d[i][j-1]) % 1000000000;
        
    cout << d[n][k] << endl;

    return 0;
}