2225번

2225번 - 합분해

처음에 0부터 N까지 수를 하나씩 뽑아보면서 완전 탐색을 실행하였다.

그러다보니 N의 K제곱이 되어서 너무나 많은 시간이 소요되었다. 그래서 DP로 구현하였다.

완전 탐색 할때 2차원으로 풀게되어 캐시 값도 이차원 배열로 지정하여 풀었다.

(일차원으로 풀어보려고 했지만, 정보가 부족해서 캐시에 담을 수가 없었다. 일차원으로 궁금해서 풀어보려고 노력했지만 난 실패)

D[K][N] = K개를 뽑아서 N을 만드는 경우의 수

라는 점화식을 세우고 

D[K][N] 에서 어떤 수 A (단, A는 0~N 사이의 값) 을 뽑았다고 했을 때, 

D[K][N} = D[K-1][N-A] 가 된다는 점을 고려해서 문제를 풀 수 있었다.

근데 사실 아직 까지도 기저 사례를 명확히 하지 않아 몇번을 수정하는 안 좋은 점을 고쳐야겠다.

<완전 탐색 코드 - 시간 초과>

 
#include<iostream>
#define div 1000000000;
using namespace std;
int N, K;
int ans;
void go(int k, int sum)
{
    if (k < 0)
    {
        return;
    }
    if (sum > N)
    {
        return;
    }
    if (sum == N && k==0)
    {
        ans += 1;
        ans %= div;
        return;
    }
    for (int i = 0; i <= N; i++)
    {
        go(k - 1, sum + i);
    }
    return;
}
int main()
{
    cin >> N >> K;
    go(K, 0);
    cout << ans << endl;
    return 0;
}

< 정답 코드 - DP >

#include<iostream>
#include<string.h>
#define div 1000000000;
 
using namespace std;
 
int N, K;
int ans;
int D[201][201];
int go(int k, int n)
{
    if (k < 0)
    {
        return 0;
    }
 
    if (n < 0)
    {
        return 0;
    }
 
    if (n == 0 && k==0)
    {
        return 1;
    }
    if (D[k][n] != 0)
    {
        return D[k][n];
    }
 
    for (int i = 0; i <= N; i++)
    {
        D[k][n] += go(k - 1, n - i);
        D[k][n] %= div;
    }
 
    return D[k][n];
}
int main()
{
    cin >> N >> K;
 
    memset(D, 0, sizeof(D));
 
    cout << go(K, N) << endl;
 
    return 0;
}