[BOJ/백준][Gold5] 2011 : 암호코드 (C++)

https://www.acmicpc.net/problem/2011

2011번: 암호코드

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[i] : s가 길이 n인 암호 문자열일 때, s[i..n-1] 로 만들 수 있는 해석의 총 개수.

 

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
int dp[5001];
string s;
int sol(int n){
    if(n>=s.size()) return 1;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    if(s[n]=='0') return 0;
    ret=sol(n+1);
    if(n+1<s.size()){
        int k = (s[n]-'0')*10+(s[n+1]-'0');
        if(k<27) ret=(ret+sol(n+2))%1000000;
    }
    return ret;
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2011.cpp