11057번

11057 - 오르막수

완전 탐색으로 구현후, 메모이제이션을 이용해 DP로 변환

앞서 풀어봤던 10844번과 매우 흡사한 문제 , 점화식이 똑같다.

D[N][L] = N자릿수이고 끝 수가 L인 오르막 수의 갯수.

10844번과는 다르게 첫번째 수가 0이 될수 있고, 숫자가 갈수록 커지기만 하면 된다는 사실.

항상 나는 캐시 값(D[N][L]) 을 -1로 초기화 했었는데, 이번 문제의 경우 기존 값에 덧셈이 필요해서 0으로 초기화 시켰다.

이 부분을 스스로 문제 풀면서 유의해야 할 것 같다.

어떤 문제는 0으로 풀면 안될 때가 있고, -1로 풀면 안될 때가 있고... 유의하자!

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

#include<iostream>
#include<string.h>
 
#define mod 10007;
using namespace std;
 
int ans;
 
 
void go(int n, int num)
{
    if (n == 1)
    {    
        ans += 1;
        ans %= mod;
        return ;
    }
 
    for (int i = num; i >= 0; i--)
    {
        go(n - 1, i);
    }
 
    return;
 
}
 
int main()
{
    int N;
    cin >> N;
 
    for (int i = 0; i < 10; i++)
    {
        go(N, i);
    }
 
    cout << ans << endl;
 
    return 0;
}

<정답 코드> <--DP구현

#include<iostream>
#include<string.h>
 
#define mod 10007;
using namespace std;
 
int ans;
int D[1001][10];
 
int go(int n, int num)
{
    if (n == 1)
    {    
        return 1;
    }
 
    if (D[n][num] != 0)
    {
        return D[n][num];
    }
 
    for (int i = num; i >= 0; i--)
    {
        D[n][num] += go(n - 1, i)%mod;
    }
 
    return D[n][num];
 
}
 
int main()
{
    int N;
    cin >> N;
    memset(D, 0, sizeof(D));
    for (int i = 0; i < 10; i++)
    {
        ans += go(N, i)%mod;
    }
 
    ans %= mod;
    cout << ans << endl;
 
    return 0;
}