백준 2011번 : 암호코드 in Python

2011번: 암호코드

 

www.acmicpc.net

이 문제는 어떤 암호가 주어졌을 때 그 암호의 해석이 몇 가지가 나올 수 있는지를 구하는 문제이다. A는 1, B는 2, ... , Z는 26으로 해석한다.

이를 해결하기 위해서 dynamic programming을 이용한다. 즉, 암호의 길이가 N일 때 i = 1부터 i = N까지 암호에서 i번째 숫자까지 봤을 때 가능한 암호 해석의 경우의 수를 저장하면서 순서대로 구한다. 이때 만약 암호에서 i번째 숫자까지 봤을 때 가능한 암호 해석의 경우의 수는 크게 두 가지 경우를 고려하면 되는데, 먼저 i번째 숫자를 하나의 문자로 해석하는 경우와 i-1번째 숫자와 i번째 숫자를 합쳐 하나의 문자로 해석하는 경우가 있다. 전자의 경우에는 i번째 숫자가 0이 되면 안 될 것이다. 후자의 경우에는 i-1번째 숫자가 1이 되거나, i-1번째 숫자가 2가 되고 i번째 숫자가 0~6일 경우에만 가능하다. 이때 전자의 경우의 수는 i-1번째 숫자까지 봤을 때 가능한 암호 해석의 경우의 수와 같을 것이다. 후자의 경우의 수는 i-2번째 숫자까지 봤을 때 가능한 암호 해석의 경우의 수와 같을 것이다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
secret = input().strip()
dp = [0 for _ in range(len(secret)+1)]
# 초기값 설정
dp[0] = 1
dp[1] = 1
# 수가 0인 경우는 암호 해석이 불가능하므로 0을 출력한다. 
if int(secret[0]) == 0:
    print(0)
else:
    for i in range(2, len(secret)+1):
        c = secret[i-1]
        d = secret[i-2]
        # 두 개의 숫자를 하나의 문자로 해석하는 경우
        if int(d) == 1 or (int(d) == 2 and int(c) <= 6):
            dp[i] += dp[i-2]
        # 하나의 숫자를 하나의 문자로 해석하는 경우
        if int(c) > 0:
            dp[i] += dp[i-1]
    print(dp[len(secret)]%1000000)