백준 2011 암호코드 / C++

문제 : 2011

풀이 point

두가지 경우가 있다.

dp[i] (여기서 i는 자리수이다.)

1. 경우의 수가 그대로인 경우

   dp[i] = dp[i-1]
   예를들면, 31인 경우에는 3만 있을 때 경우의 수와 31일때 경우의 수는 다르지 않다.

2. 경우의 수가 늘은 경우

   dp[i] += dp[i-2]
   예를들면, 312인 경우에는 31일때 경우의 수 + dp[i-2]의 값을 더해주면 된다.(3일때 경우의 수)

단, 1번 경우일 때는 0은 포함되지 않는다.(0은 단독으로는 불가능하기 때문)
2번 경우일 때는 10과 26사이어야한다.

코드

//백준 2011, 암호코드

#include <iostream>

#define mod 1'000'000

int dp[5001];

int main (){

    std::string s;
    std::cin >> s;

    if(s[0] == '0'){
        std::cout << 0;
        return 0;
    }

    dp[0] = 1; dp[1] = 1;
    for(int i{2}; i<=s.size(); ++i){
        if(s[i-1] != '0') dp[i] = dp[i-1]%mod;
        int tmp = (s[i-2]-'0')*10 + (s[i-1]-'0');
        if(tmp >= 10 && tmp <= 26) dp[i] += dp[i-2]%mod;
    }

    std::cout << dp[s.size()]%mod;

    return 0;
}