[Gold 5] 2225 합분해

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

이 문제는 DP를 사용하는 해결할 수 있다.

0부터 N까지의 수 중에 K개의 숫자를 사용해서 N을 만드는 문제이다.

 

이 문제를 보고 6, 4에 대해 직접 경우의 수를 세워 봤을 때 다음과 같은 표의 결과가 나왔다.

	K = 1	K = 2	K = 3	K = 4
N = 1	1	2	3	4
N = 2	1	3	6	10
N = 3	1	4	10	20
N = 4	1	5	15	35
N = 5	1	6	21	56
N = 6	1	7	28	84

 

위 표를 보면 (2,2)의 경우 (2,1) + (1,2)의 합인 것을 볼 수 있다.

따라서 (6,4) = (6,3) + (5,4)라는 것을 알 수 있다.

 

이를 바탕으로 점화식을 세우면 다음과 같다.

DP[N][K] = DP[N-1][K] + DP[N][K-1]

 

위 점화식을 적용시킬 수 있는 범위는 (2,2)부터 (N,K)까지이다.

따라서 K = 1일 때 DP 배열을 모두 1로 초기화하는 과정과 N = 1일 때 DP 배열을 1식 증가시키는 과정이 필요하다.

위 과정을 모두 이루어냈다면 위 점화식을 적용하면 문제를 해결할 수 있다.

 

 

#include<iostream>
#include<cstring>
using namespace std;

int N,K;
int dp[201][201];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
    cin>>N>>K;

    // K가 1인 경우 초기화
    for(int i = 1;i<=N;i++)
        dp[i][1] = 1;
    
    for(int j = 2;j<=K;j++)
        dp[1][j] = (dp[1][j-1] + 1) % 1000000000;

    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;
    }
    cout<<dp[N][K]<<'\n';
    
    return 0;
}