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

문제

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

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

 

입력

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

 

출력

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

---

DP를 이용하여 풀 수 있는 문제.

문제 이해를 잘못해서..(잘 못해서 X, 잘못 해서 O) 고생을 많이 했던 문제다..ㅠㅠ

 

예제 입력으로 주어진 20 2의 경우 20을 2개의 숫자로 더하는 경우인

20 = 0 + 20 = 1 + 19 = 2 + 18 = 3 + 17 = ... = 19 + 1 = 20 + 0 의 경우를 모두 더하여 답이 21이 된다.

 

long long 자료형의 2차원 배열 arr[][]을 선언해준다. arr[i][j]에는 i번 더하여 j를 만들 수 있는 경우의 수가 들어간다. i가 1일 경우, 즉 j를 한번만 더하여 만들 수 있는 경우의 수는 j 그 자체 한 가지 뿐이므로 arr[1][j]는 모두 1로 초기화해준다.

 

j = (j - m) + m (0 ≤ m ≤ j)인 점을 이용하였을 때, i번 더하여 j를 만들 수 있는 경우는 (i - 1)번 더하여 m(또는 (j - m))을 만들 수 있는 경우의 수와 같기 때문에, 점화식은 다음과 같은 식으로 표현할 수 있다.

 

for(int i = 2; i <= k; i++) {
   for(int j = 0; j <= n; j++) {
       for(int m = 0; m <= j; m++) {
            arr[i][j] += arr[i - 1][m];
        }
    }
}

 

주의할 점은..MOD(1,000,000,000)를 올바른 위치에 넣어 나머지 연산을 해야한다. 이걸로 두번이나 틀렸다.

전체 코드는 다음과 같다.

 

코드

#include <cstdio>
#define MOD 1000000000

long long DP(int n, int k);

int main(void) {
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%lld\n", DP(n, k));
    return 0;
}

long long DP(int n, int k) {
    long long arr[201][201] = { 0 };
    
    for(int i = 0; i <= n; i++) {
        arr[1][i] = 1;
    }

    for(int i = 2; i <= k; i++) {
        for(int j = 0; j <= n; j++) {
            for(int m = 0; m <= j; m++) {
                arr[i][j] += arr[i - 1][m];
                arr[i][j] %= MOD;
            }
        }
    }
    return arr[k][n];
}