[DP] 백준 2225 합분해 (개수가 주어진 문제)

 합분해 성공 풀이

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	5062	2171	1634	42.630%

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1≤N≤200), K(1≤K≤200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 

20 2

예제 출력 

21

---

합분해 문제

문제에서 어려웠던 점 

• 어떻게 풀어야 하는지 전혀 파악이 안되었다. 

푸는 Logic

N이라는 숫자를 만들기 위해서 K개수의 숫자가 필요하다 

O + O + O .... + O = N

여기서 맨 마지막 수를 L 이라고 한다면 

O + O + O .... + O = N

d[k-1][n-L]     +  L

점화식은 이렇게 된다. 

L의 범위가 다음 topic 인데 

L은 N과 같을 때 가장 크고 0일 때 가장 작다. 

#include <iostream>

using namespace std;

int d[201][201];

int main(void)

{

    int n, k;

    cin >> n >> k;

    d[0][0] = 1;

    for (int i = 1; i <= k; ++i) {

        for (int j = 0; j <= n; ++j) {

            for (int l = 0; l <= j; ++l) {

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

                d[i][j] %= 1000000000;

            }

        }

    }

    cout << d[k][n];

    return 0;

}