합분해 백준 2225

문제

합분해 백준 2225번

리뷰

목표 합 n과 식의 개수 k를 관리하는 2차원 배열로 풀면 된다.

D[k] [n] 는 합이 n이 되는 k개의 항의 경우의 수를 저장한다.

D[2] [2] 는 합이 2가 되는 2개의 항의 경우의 수를 저장한다.

예를 들어, 0 + 2, 1 + 1, 2 + 0 이 있다. D[2] [2] = 3 이 저장된다.

목표합이 0 일 때, 항은 전부 0개 필요하다.

목표합이 1일 때, 항은 전부 그 숫자 1개가 필요하다. 따라서 아래와 같이 초기화 해준다.

     for(i = 0; i <= n; i++){   // 목표합이 i일 때, 항의 개수를 1개로 표현하면, 
        D[1][i] = 1; 
    }

2개의 항으로 3을 만드는 경우를 생각해보자.

k = 2, n = 3 이다.

0 + 3 -> 1개의 항으로 0이 되는 경우의 수 + 1개의 항으로 3이 되는 경우의 수

3+ 0 -> 1개의 항으로 3이 되는 경우의 수 + 1개의 항으로 0이 되는 경우의 수

2+ 1 -> 1개의 항으로 2이 되는 경우의 수 + 1개의 항으로 1이 되는 경우의 수

1+ 2 -> 1개의 항으로 1이 되는 경우의 수 + 1개의 항으로 2이 되는 경우의 수

이렇게 4가지 경우가 있으니까, D[2] [3] = 4 가 된다.

D[2] [3] = D[1] [0] + D[1] [1] + D[1] [2] + D[1] [3]

따라서 k=2 일 때, k-1 개의 항으로 0이 되는 경우의 수, 1이 되는 경우의 수, + ... n 이 되는 경우의 수를 더해야 한다.

D[k] [n] = D[k-1] [0] + D[k-1] [1] + ... + D[k-1] [n-1] + D[k-1] [n]

코드로 나타내면 3중 for문이 된다.

D[i] [j] 를 저장하기 전에 mod 연산이 필요하다는 것을 유의해야 한다.

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){  // 0부터 목표 합까지 
                D[i][j] += D[i-1][s];
            }
            D[i][j] =  D[i][j] % MODNUM;
        }
    }

코드

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

#define N_MAX 201
#define K_MAX 201
#define MODNUM 1000000000

// 2225  합분해  

long long D[N_MAX][K_MAX];  // MODNUM 으로 mod 연산 할꺼니까 long long형  

int main(void){

    int n, k = 0;
    int i, j, s = 0;

    scanf("%d %d", &n, &k); // 목표합, 항의 개수  

     for(i = 0; i <= n; i++){  // 목표합이 i 일 때, 1개 항으로 나타내는 경우의 수  
        D[1][i] = 1; 
    }

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){ 

                D[i][j] += D[i-1][s];
            }

            D[i][j] =  D[i][j] % MODNUM;
        }
    }

    printf("%lld", D[k][n]); 

    return 0;
}