백준 2011 - 암호코드

문제

 

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

2011번: 암호코드

 

 

풀이

 

N자리의 암호가 주어질 때 N번째에 올 수 있는 암호는 1부터 9까지이고, N-1과 N번째에 10부터 26까지 올 수 있다. 

예를 들어, 5자리 암호 ○○○○● 일때 ●에는 1부터 9까지 올 수 있고, ○○○●● 에서 ●●에는 10부터 26까지 올 수 있다.

 

따라서 d[n] = n자리 암호를 해석할 수 있는 가짓수 라고 할때,

기본적으로 d[n] = d[n-1](1~9가 올 경우) + d[n-2](10~26이 올 경우) 이 된다.

 

하지만 암호가 되지 않는 경우도 있는데 암호의 시작에 0이 들어가거나 0이 두번 연속 나오게 되면 암호가 될 수 없고, 또한 암호 중간에 0이 들어가면 10 또는 20으로만 해석을 해야해서 이에 대한 예외 처리가 필요하다.

01234 : 암호 해석 불가능

12003 : 암호 해석 불가능

12034 : 0 때문에 20으로만 해석 가능

 

그리고 두 자리 암호를 해석할 경우 해석된 숫자가 26이하일 경우에만 추가를 해야한다.

 

 

코드

 

#include <iostream>
#include <string>
 
using namespace std;
 
string N;
int dp[5001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
 
    // 암호의 시작이 0일 경우 해석 불가능
    if (N[0] == '0') 
    {
        cout << 0;
        return 0;
    }
 
    dp[0] = dp[1] = 1;
    
    for (int i = 2; i <= N.size(); i++)
    {
        char a = N[i - 1], b = N[i - 2];
        if (a == '0' && b =='0')    // 두 자리 연속 0인지 검사
        {
            cout << 0;
            return 0;
        }
        if (a != '0') dp[i] += dp[i - 1];   // i번째 숫자가 0이 아닐 경우 한 자리 숫자가 가능
        if (b != '0')   // i-1 번째 숫자가 0이 아닐 경우 두 자리 숫자가 가능
        {
            int num = (b - '0')*10 + (a - '0');
            if (num <= 26) dp[i] += dp[i-2];
        }
        dp[i] %= 1000000;
    }
 
    cout << dp[N.size()];
    return 0;
}