[알고리즘] 합분해

구현 방식

• acc[k][n] 을 정수 k 개를 더해서 합이 N이 되는 경우의 수를 말한다고 할 때
• 아래의 사진과 같이 acc[k][n] 아래의 합과 같다.
  • i 가 0 일 때 만들 수 있는 경우의 수는 acc[k-1][n] 개
  • i 가 1 일 때 만들 수 있는 경우의 수는 acc[k-1][n-1] 개
  • …
  • i 가 n 일 때 만들 수 있는 경우의 수는 acc[k-1][0] 개

코드

• 코드는 아래와 같다.

int DP(int N, int K)
{
    vector<vector<int>> acc = vector<vector<int>>(K + 1, vector<int>(N+1,1));

    for (int k = 2; k <= K; k++ )
    {
        for (int n = 1; n <= N; n++)
        {
            acc[k][n] = 0;
            for (int i = 0; i <= n; i++)
            {
                acc[k][n] += acc[k - 1][i];
                acc[k][n] %= 1000000000;
            }

        }
    }

    return acc[K][N];
}