[백준 2011] 암호코드 (DP) (C/C++) (★)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
#define MOD 1000000
 
string N;
long long dp[5010];
 
long long solve(int idx)
{
    if(idx >= N.size())
    {
        return 0;
    }
    else if(idx == N.size()-1)
    {
        return 1;
    }
    
    if(dp[idx] != 0)
    {
        return dp[idx];
    }
    
    if('1' <= N[idx+1])
    {
        dp[idx] = solve(idx+1) % MOD;    
    }
    
    if((N[idx+1] == '1') || (N[idx+1] == '2' && N[idx+2] <= '6'))
    {
        dp[idx] = (dp[idx] + solve(idx+2)) % MOD;    
    }
    
    return dp[idx];
}
 
int main(void)
{
//    freopen("B2011_input.txt", "r", stdin);
    
    cin >> N; 
    
    N = "0" + N;
    
    cout << solve(0);
    
    return 0;
}