백준 2225 - 합분해(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2225

2225번: 합분해

점화식을 이용한 DP 문제였습니다.

점화식을 새울 수 있다면 쉽게 풀 수 있는 문제였습니다.

N, K의 값을 입력받은 뒤, N을 K개의 합으로 만들 수 있는 경우의 수를 구하는 문제입니다.

이때, 주의할 점은 1+(N-1)과 (N-1)+1은 다른 경우로 취급한다는 것입니다.

 

에시를 하나 들어보겠습니다.

(X, Y)는 X를 Y개로 만드는 경우라고 하겠습니다.

N = 3, K = 3인 경우로 생각해보겠습니다.

(0, 1) + (3, 2) / (1, 1) + (2, 2) / (2, 1) + (1, 2) / (3, 1) + (0, 2)

(0, 2) + (3, 1) / (1, 2) + (2, 1) / (2, 2) + (1, 1) / (3, 2) + (0, 1) 

해당 경우로 나눌 수 있습니다.

 

여기에서 확인할 수 있는 것은 (0, 1) (0, 2) (1, 1) (1, 2) (2, 1) (2, 2) (3, 1) (3, 2)가 나오는 것을 볼 수 있습니다.

 

이를 통해서 알 수 있는 것은

N을 만들기 위해서는 (N - M) + M을 해야되는데, 이때 M은 N을 만들어 주는 수입니다. 

결국에는 (N - M)들의 경우의 수 합이 N의 경우의 수가 된다는 것입니다.

 

위의 예시에서는, (0, 2) / (1, 2) / (2, 2) / (3, 2)의 합이 될 것입니다.

 

이를 N과 K로 치환해서 생각해보면,

Sum[K][N] = Sum[K-1][0] + Sum[K-1][1] + ..... + Sum[K-1][N] 이 됩니다.

해당 식이 점화식이며, 이 식을 통해 문제를 풀 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>
#define P pair<int, int>
#define F first
#define S second
#define INF 1000000000

using namespace std;

int N, K;
long long Sum[201][201]; // X개 더해서 Y 나오는 수

void solve(){
    for(int i = 0; i <= N; i++){
        Sum[1][i] = 1;
    }
    for(int k = 2; k <= K; k++){
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= i; j++){
                Sum[k][i] += Sum[k-1][j];
            }
            Sum[k][i] %= INF;
        }
    }
    cout << Sum[K][N];
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    solve();
    return 0;
}

 

 

 질문 및 조언은 댓글 남겨주세요