[백준][2011번][DP] 암호코드

암호코드

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

<코드>

#include <stdio.h>
#include <string>
using namespace std;
#define mod 1000000
int main(void){
 
    char secret[5001];
    int secretSize;
    int Dp[5010] = {};
    Dp[0] = 1;
    Dp[1] = 1;
    string s;
    scanf("%s", secret);
    s = secret;
    secretSize = s.size();
 
    for (int i = 2; i <= secretSize; i++)
    {
        int now = i - 1;
        if (secret[now] > '0')
            Dp[i] = Dp[i - 1] % mod;
 
        int x = (secret[now- 1]-'0') * 10 + secret[now]-'0';
        
        if (10 <= x && x <= 26)
            Dp[i] = (Dp[i] + Dp[i - 2]) % mod;
    }
    
    printf("%d\n", Dp[secretSize]);
 
}

<문제 푼 요령>

1. 이 문제의 중요성은 예외를 잘 파악하는 것과 경우의 수를 잘 파악하는 것에 있다.  

2. 예외적인 사항은 지금의 값이 '0' 일때 예외가 될 수 있다. 왜냐하면 0에 알파벳은 존재하지 않기 때문에. 그리고 지금의 숫자와 앞의자리의 숫자가 10~ 26사이의 숫자면 경우의 수가 추가된다.

3. 그래서 경우의 수를 따져보면

- secret[i] > 0 이라면  : 이전의 숫자의 경우의 수를 가져온다 왜냐하면 secret[i]가 알파벳 한자리 수 나온다는 거니까 1 * 이전 자리수까지의 경우의 수가 되서이기 때문이다.

- secret[i-1] *10 + secret[i] 가 10 이상 26이하일 경우 : 이럴 때는 경우의 수가 추가되는데 Dp[i-2]의 경우의 수를 한번 더 추가하는 것과 같기 때문에 Dp[i-2] * 1 의 경우의 수를 더해주면된다.

4. 이런 방식으로 진행하면 마지막에 얻는 값이 최대 가지수가 나온다.