[ALGORITHM] 백준 2011 - 암호코드

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

2011번: 암호코드

과정

1. 시작이 0인지 판단
2. 시작이 10 혹은 20인 경우를 위해 dp[1]과 dp[0]을 1로 변경(현재 자리가 0인 경우 i-2번째 값을 참조하기 때문에)
3. 만약 현재 자리가 0인 경우
   1. 이전 자리가 3인 경우 종료
   2. 아닌경우 dp[i]계산
4. 0이 아닌 경우
5. dp[i] 계산
6. 만약 26이하 10이상인 경우
7. dp[i] 추가 계산

주의할 점

구현과 dp가 섞인 까다로운 문제이다. 

0과 관련된 처리가 제대로 되었는지 확인하자

 

코드

#include<iostream>
#include<string>

using namespace std;

string str;
int len;
int dp[5001];
int mod = 1'000'000;

void init(){
    fill(&dp[0],&dp[5000],0);
}

void input(){
    cin>>str;
    len=str.length();
}


void solution(){
    if(str[0]=='0'){
        cout<<0<<'\n';
        return ;
    }
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=len;++i){
        if(str[i-1]=='0'){
            if(str[i-2]=='0'||str[i-2]>='3'){
                cout<<'0'<<'\n';
                return;
            }
            else{
                dp[i]=(dp[i-2])%mod;
            }
        }
        else{
            dp[i]=(dp[i-1])%mod;
            string tmp="";
            tmp+=str[i-2];
            tmp+=str[i-1];
            if(tmp<="26"&&tmp[0]>='1'){
                dp[i]+=(dp[i-2])%mod;
            }
        }
    }
    cout<<dp[len]%mod<<'\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    input();
    solution();

    return 0;
}