10844번

10844번 - 쉬운 계단 수

DP를 이용해서 풀었다.

처음에 완전탐색으로 풀고, 시간초과로 인해 메모이제이션을 사용하는 DP로 풀게 됐다.

이차원 DP를 이용해서

D[N][L] = N자릿수, 마지막 숫자가 L인 쉬운 계단 수의 가짓수.

이 문제에서 발견한 나의 실수 2가지

1. 아직도 기저 사례에 대해서 완벽하게 하지 않고 풀었다.

=> 이번 문제의 경우 N이 1일 때, 첫번째 자리에 0이 들어가면 안된다는 조건을 까먹고 자꾸 갯수가 +1 되는 것을 처음부터 생각하지 못함.

2. int값을 벗어나는 변수일 경우, long long 타입을 해줘야 하는데 그걸 잊었다. 삼성 기출 문제에서도 이런식으로 변수값을 벗어나는 문제가 있었는데

그때도 틀렸던 점을 다시 잊고 틀렸다.

<정답 코드>

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