[C++] 백준 - 2011 : 암호코드

문제 링크

2011번: 암호코드

 

풀이 ) DP

  문자열로 입력을 받은 후 다음 case로 나눈다.

• 0인 경우(00) : 불가능
• 한자리 수인 경우(01~09) : 뒤의 한자리를 제외한 n-1자리로 만든 경우의 수
• 26이하인 경우 중 10의 배수인 경우 : 뒤의 두 자리를 제외한 n-2자리로 만든 경우의 수
• 26이하인 경우 중 10의 배수가 아닌 경우 : 뒤의 한자리와 두 자리를 제외한 n-1, n-2자리로 만든 경우의 수의 합
• 27이상인 경우 중 10의 배수인 경우 : 27이상의 숫자로도 만들 수 없고 끝이 0이므로 불가능
• 27이상인 경우 중 10의 배수가 아닌 경우 : 뒤의 한자리를 제외한 n-1자리로 만든 경우의 수

 

#include <cstdio>
#include <string.h>

int memo[5001] = {1, 1};

int main(void)
{
    char p[5001] = "";
    scanf("%s", p);

    if(p[0] == '0'){
      printf("0\n");
      return 0;
    }
    for(int i = 2; i <= strlen(p); i++){
        int num = (p[i-2]-'0')*10 + p[i-1]-'0';
        if(num == 0){
            printf("0\n");
            return 0;
        }
        else if(num < 10){
            memo[i] = memo[i-1];
        }
        else if(num < 27){
            if(p[i-1] == '0'){
                memo[i] = memo[i-2];
                continue;
            }
            memo[i] = memo[i-1]+memo[i-2];
        }
        else{
            if(num%10 == 0){
                printf("0\n");
                return 0;
            }
            memo[i] = memo[i-1];
        }
        memo[i] %= 1000000;
    }
    printf("%d\n", memo[strlen(p)]);
    return 0;
}

주의점 )

  - memo 배열을 초기화할 때 처음 두 원소를 1, 1로 초기화해주어 두 자리 이상에 대하여 memo[i-1]과 memo[i-2]를 모두 구할 수 있도록 해주어야 한다.

  - 0이 입력되는 경우를 위해 예외처리를 해준다.