백준 2225번. 합분해(c++) / DP

DP...역시 쉽지 않다.

예전에 풀었던 동전 문제와 유사해서 점화식을 비교적 쉽게 세울 수 있었다.

DP[선택한 수의 개수][총 합]이라고 가정했을 때

DP[k][n]을 만들기 위해서 맨 마지막에 뽑은 수가 L이라고 한다면,

DP[K][N] = Σ(DP[K-1][N-L])
L => 0 <= L <= N

위와 같은 식이 나오는 것을 알 수 있다.

이 점화식을 바탕으로 코드를 구현하면 다음과 같다.

 

// 합분해
#include <iostream>
using namespace std;
 
int n, k;
long long dp[201][201] = {0, }; // (합, 갯수)
 
int main()
{
    cin>>n>>k;
    
    // 1개 선택했을 때
    for(int i=0; i<=n; i++){
        dp[1][i] = 1;
    }
 
    for(int i=1; i<=k; i++){
        for(int j=0; j<=n; j++){
            for(int k=0; k<=j; k++){
                dp[i][j] += (dp[i-1][j-k]%1000000000);
            }
        }
    }
    
    cout<<dp[k][n]%1000000000<<"\n";
 
    return 0;
}