[골드 V] 2011번. 암호코드

 문제 

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

2011번: 암호코드

 사용 언어 

Python3

 풀이 과정 

또다른 동적 프로그램 문제였다. 처음 아이디어는 금방 생각 했는데 코드로 구현하는데는 좀 오래걸렸던 것 같다.

특히 경우의 수를 제대로 나누는 것이 어려웠는데, 일단 0으로 시작하는 경우만 걸러주고 이후에 해독이 안되는 코드는 자동으로 걸러지도록 경우를 나누었다.

 

if code[0] == 0: # 0으로 시작하면 잘못된 코드

else:
    # 이후 한 자리, 아니면 두 자리로 해독가능한 코드인지 확인

6번만에 본 맞았습니다!!

 제출 답안 

from sys import stdin

# A = 1, B = 2, C = 3... Z = 26
# 한 자리수 아니면 두 자리수
# 두 자리수의 경우 27부터는 불가능

# 한 자리 수 : convert[x] = convert[x-1] + convert[x]
# 두 자리 수 : convert[x] = convert[x-2] + convert[x]

code = list(map(int, stdin.readline().strip()))
l = len(code)
dp = [0 for _ in range(l+1)]

if code[0] == 0: # 0으로 시작하면 잘못된 코드
    print("0")
else:
    code = [0] + code # 인덱스 맞춰주기 위해
    dp[0] = dp[1] = 1
    for i in range(2, l+1):
        if code[i] > 0:
            dp[i] += dp[i-1]
        temp = code[i-1] * 10 + code[i] # 앞자리와 합쳐줌
        if temp >= 10 and temp <= 26:
            dp[i] += dp[i-2]
    print(dp[l] % 1000000)