[Python] 2011번 : 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

예제 입력 1

25114

예제 출력 1

6

예제 입력 2

1111111111

예제 출력 2

89

예제 입력 3

001

예제 출력 3

0

 

예제 입력 4

8100

예제 출력 4

0

예제 입력 5

9

예제 출력 5

1

예제 입력 6

1203

예제 출력 6

1

 

소스코드

num = input()
val = True	# 0이 중간이나 끝에 들어가는 경우 중 불가능한 경우를 골라내기 위한 변수
if not str.isdigit(num) or num[0]=='0':	# 입력받은 num 문자열에 숫자가 아닌 값이 있거나 '0'으로 시작하는 경우 0을 출력하도록 함
    print(0)
else:	# 암호를 해석할 수 있는 경우
    n = list(map(int, num))	# 입력받은 문자열을 문자 리스트로 바꿈
    while 0 in n:	# 0이 들어있는 경우, 앞 문자와 합하여 10또는 20으로 만들어줌
        idx = n.index(0)
        n[idx-1] = int(str(n[idx-1]) + str('0'))
        del n[idx]

    for i in range(len(n)):	# 0이 앞 문자와 합쳐졌을 때 1~26 범위를 벗어나는 경우가 발생하면 0을 출력함
        if n[i] <= 0 or n[i] > 26:
            print(0)
            val = False	# 예외가 존재함을 알려줌
            break
    
    if val:	# 예외에 해당되지 않는 경우
        m = len(n)
        dp = [[0] * 2 for _ in range(m+1)]	# dp[i][0] : i자리 수에서 맨 끝에 1자리 문자가 오는 경우, dp[i][1] : i자리 수에서 맨 끝에 2자리 문자가 오는 경우
        result = [0] * (m+1)	# result[i] = dp[i][0] + dp[i][1] -> i번째 자리에서 가능한 모든 경우의 수
        s = []	# i자리 수에서 맨 끝 문자를 저장함

        for i in range(m):
            s.append(str(n[i]))

        dp[1][0], dp[1][1] = 1, 0
        result[1] = (dp[1][0] + dp[1][1]) % 1000000
        for i in range(2, m+1):
            tmp = int(s[i-2] + s[i-1])	# i-1자리 수의 맨 끝 문자에 i번째에 추가된 문자를 더한 값이 범위 안에 존재하면 dp[i][1] = dp[i-1][1], 존재하지 않으면 dp[i][1] = 0
            if tmp <= 26:
                dp[i][1] = dp[i-1][0]
            
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            result[i] = (dp[i][0] + dp[i][1]) % 1000000

        print(int(result[m]))

dp[1][0] = 1, dp[1][1] = 0

dp[2][0] = dp[1][0] + dp[1][1], dp[2][1] = dp[1][0]

dp[3][0] = dp[2][0] + dp[2][1], dp[3][1] = dp[2][0]

.

.

.

dp[i][0] = dp[i-1][0] + dp[i-1][1], dp[i][1] = dp[i-1][0]

 

처리해야 할 반례가 많았던 문제이다.