BOJ 2225 합분해(C++)

합분해 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1508	668	491	42.622%

문제

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

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

입력

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

출력

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

예제 입력 

20 2

예제 출력 

21

힌트

알고리즘 분류

• 다이나믹 프로그래밍

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include    <stdio.h> #pragma warning(disable : 4996)   #define div 1000000000 static int D[222][222]; int main() {     int N, K;     scanf("%d %d", &N, &K);       for (int i = 0; i <= N; ++i)         D[i][1] = 1;       for (int i = 2; i <= K; ++i)     {         for (int j = 0; j <= N; ++j)         {             for (int k = 0; k <= j; ++k)                 D[j][i] = (D[j][i] + D[k][i - 1]) % div;         }     }     //D[n][k] 가 0~n을 k번 써서 만들 수 있는 방법의 수 일때     //D[n][k] = D[0][k-1] + D[1][k-1] ... + D[n][k-1] 이므로       printf("%d", D[N][K]);     return 0; }

생각이 좀 많았지만 우선 생각은 N, K를 받아 0~N까지의 수를 K번 사용하여 N을 만들 수 있는 갯수를 D[N][K]라고 정의하였다. 

정의하고 나니 분명 이전의 결과의 합이라는걸 생각하게 되었고, 사실 바로 정확한 점화식을 딱! 세워서 푼 것은 아니고.. 생각나는대로 여러번 썼다가 이게 아닌데.. 하면서 실수하다보니 식이 나왔다. 언제쯤 딱! 하고 점화식 딱 나와서 딱 코딩할수있을지 모르겠지만..ㅠ_ㅠ

우선 D[n][k] 는 D[0][k-1] + D[1][k-1] + ... + D[n][k-1] 이다. 

k인 경우는 모두 사용했기 떄문에 더이상 사용할 수 없고 

k-1인 경우에 0부터 N을 각각 한번씩 사용할 수 있기 때문에 

(D[20][2]를 구할 떄 D[0][1]은 20을 한번 사용하면 되고 D[1][1]은 19를, ... D[20][1]은 0을 사용하면된다.)

모든 경우의수라고 할 수 있다. 

그 후로는 간단.. (코드는 사실 점화식을 잘못 세운다음에 코딩을 시작해서 for문이 난잡하다..)