BOJ 2225 합분해

pa324·2019년 11월 16일
0

문제

풀이

문제를 통해서 점화식을 정의하면 아래와 같다.

dp[n][k] = n까지의 정수 k개를 더한 합이 n이 되는 경우의 수

dp[0][1] = 0
dp[1][1] = 1
dp[2][1] = 2
dp[2][2] = 0+2,1+1,2+0
dp[3][1] = 3
dp[3][2] = 0+3,1+2,2+1,3+0
dp[3][3] = 1+1+1
 (...)  +  j  =  n
 k-1개    1개
 
> dp[n][k] += dp[n-j][k-1]

코드

#include<stdio.h>
long long dp[201][201];
int main() {
    
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i = 0; i <= n; i++) {
         dp[i][1] = 1;
    }
    
    for(int i = 0; i <= n; i++) {
        for(int j = 2; j<= k; j++) {
            for(int k = 0 ; k<= i; k++) {
                dp[i][j] += dp[i-k][j-1];
                dp[i][j] %= 1000000000;
            }
        }
    }
    printf("%lld\n",dp[n][k]);
    return 0;
}


profile
안녕하세요

0개의 댓글