[백준(BOJ)] 2225번: 합분해 (Dynamic Programming, C++)

📝 문제풀이 과정

---

N/K	1	2	3	4
1	1	2	3	4
2	1	3	6	10
3	1	4	10	20
4	1	5	15	35

DP[N][K]: 0부터 N까지의 정수 중에서 K개의 수로 N을 만드는 경우의 수

DP[1][1]부터 DP[4][4]까지의 경우의 수를 구해보면, 일반화된 점화식을 구할 수 있다.

DP[i][1] = 1 : 모든 수 N에 대하여 K = 1일 때 경우의 수는 1이다. 

DP[1][i] = i : 모든 수 1에 대하여 K = i일 때 경우의 수는 i이다. 

N = 2, K = 2부터는 DP[N][K] = DP[N-1][K] + DP[N][K-1] 라는 점화식을 가질 수 있다.

j의 범위는 K 이하까지이다. (그 이후로 되면 out of range로 쓰레기 값이 나온다..)

매 DP[i][j]마다 1000000000으로 나눈 나머지를 값으로 준다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>

int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    
    int DP[N+1][K+1] = {0,};
    for(int i=1; i<=N; i++) DP[i][1] = 1; // N = i, K = 1일 때 모든 N에 대해서 항상 1
    for(int i=1; i<=K; i++) DP[1][i] = i;

    for(int i=2; i<=N; i++){
        for(int j=2; j<=K; j++){
            DP[i][j] = (DP[i-1][j] + DP[i][j-1]) % 1000000000;
            //printf("DP[%d][%d]: %d\n", i, j, DP[i][j]);
        }
    }
    printf("%d", DP[N][K]);
    
}

 

 

👏 결과

---