2225-합분해 (DP 최적화)

합분해

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	8577	3709	2751	42.473%

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

20 2

예제 출력 1 

21

문제 정의

D[N][k] : N을 k개의 정수의 조합의 합으로 나타낼 수 있는 모든 경우의 수

점화식

N =  ... + p

N = ( ... = N-p, k-1개) + p

D[N][k] = ∑(D[N-p][k-1])

조건

0<=p<=N

연산 복잡도 O(N^2*K)

위의 접근법에서 중복연산을 잡아낼 수 있으면, 복잡도를 더 낮출 수 있을 것이다.

불가피한 수반 과정인, 배열 원소에 접근에 대한 복잡도 O(N*K)를 제외하면, N의 연산이 추가로 발생하고 있다.

원인은 ∑연산이다. 이를 최적화 하기 위해서는 시그마 연산을 단순화 할 수 있는지 확인할 필요가 있다.

0부터 N까지, 정수 k개를 더해서 그합이 N이되는 모든 경우의 수를 알아내기위해 ∑(D[i-p][j-1]) 연산이 사용된다.

∑연산을 풀어보면, D[N][k] = D[0][k-1] + D[1][k-1] + D[2][k-1] + ... + D[N-1][k-1] + D[N][k-1]이다.

그런데, D[N-1][k] = D[0][k-1] + D[1][k-1] + ... + D[N-1][k-1] 이므로, Bottom up과정에서 중복된 연산이 발생하고 있었음을 알 수 있다.

따라서, D[N][k] = D[N-1][k] + D[N-1][k-1]로 바꿀 수 있다. 이때, 각 항은 1의 복잡도를 가진다. D[N-1][k]가 이미 계산되어 있었기 때문이다.

이로인해, ∑로 생긴 O(N)의 복잡도를 O(1)로 낮출 수 있다.

결국 이러한 식을 적용하면, O(Nk)의 복잡도로 낮출 수 있다.

#include <iostream>
 
using namespace std;
 
long long int D[201][201];
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, k;
    cin >> N >> k;
 
    D[0][0] = 1;
 
    for (int i = 0; i <= N; i++)
        for (int j = 1; j <= k; j++)
        {
            if (i == 0)
            {
                D[i][j] = D[i][j - 1];
                continue;
            }
            D[i][j] = (D[i][j] + D[i][j - 1]) % 1000000000 ;
            D[i][j] = (D[i][j] + D[i - 1][j]) % 1000000000;
        }
            //for (int p = 0; p <= i; p++)
            //{
            //    D[i][j] += D[i - p][j - 1];
            //    D[i][j] %= 1000000000;
            //}
 
    cout << D[N][k];
    return 0;
}

#include <iostream>
 
using namespace std;
 
long long int D[201][201];
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, k;
    cin >> N >> k;
 
    D[0][0] = 1;
 
    for (int i = 0; i <= N; i++)
        for (int j = 1; j <= k; j++)
        {
            if (i == 0)
            {
                D[i][j] = D[i][j - 1];
                continue;
            }
            D[i][j] = (D[i][j] + D[i][j - 1]) % 1000000000 ;
            D[i][j] = (D[i][j] + D[i - 1][j]) % 1000000000;
        }
            //for (int p = 0; p <= i; p++)
            //{
            //    D[i][j] += D[i - p][j - 1];
            //    D[i][j] %= 1000000000;
            //}
 
    cout << D[N][k];
    return 0;
}