[C/C++] 백준 #2011 암호코드(동적 계획법)

영문 대문자로만 이루어진 암호가 있으면, 해당 영문자를 A는 1로 B는 2로 Z는 26으로 차례대로 숫자를 지정한다면, 숫자를 나열할 수 있습니다.  예를 들어서 BEAN은 B는 2, E는 5, A는 1, N은 14이므로 25114로 표현할 수 있죠.  하지만, Y = 25, K = 11, D = 4 이므로 YKD도 될 수 있죠.  숫자가 주어졌을 때, 그것을 영문자로 바꿀 수 있는 경우는 제한되어 있습니다.

 

Enigma

 

일단 0을 제외한 한자리 숫자는 모두 영문으로 만들 수가 있겠죠.  두자리 숫자가 26을 초과한다면 이 경우에는 J 이상의 영문자로 만들 수가 없으므로 한자리 숫자로 해야 합니다.  그리고 바꿀 수 없는 경우도 있습니다.  304와 같은 숫자는 나올 수 있는 영문 단어가 없습니다.  30은 글자가 안 되고, 0 역시 글자가 안 되니까요.  이런 특수한 경우를 잘 고려해서 작성하시면 됩니다.

 

최대로 보관해야 하는 경우의 수는 이전 한가지이므로 피보나치 수열을 만들 때, 두개의 변수를 이용하듯이 여기서도 사용하면 5,000개의 배열을 사용하지 않아도 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2011 - Password Code
//        - by Aubrey Choi
//        - created at 2019-06-16
//------------------------------------------------
#include <stdio.h>

int main()
{
    char enigma[5010];
    int a = 1, b = 1, t, s;
    scanf("%s", enigma);
    s = enigma[0] - '0';
    if(s == 0) a = b = 0;
    for(int i = 1; enigma[i]; i++)
    {
        s = (s % 10) * 10 + enigma[i] - '0';
        if(s <= 26)
        {
            if(s % 10 == 0) b = a, a = 0;
            else t = b, b = (a + b) % 1000000, a = t;
        }
        else if(s % 10 == 0) a = b = 0;
        else a = b;
    }
    printf("%d\n", b);
}