[백준/2011] 암호코드 (Python)

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

2011번: 암호코드

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:08:37

 

---

 

문제 설명

 

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

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

 

입력 및 출력

 

입력

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

 

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.
암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

 

입력 예시

 

25114

 

출력 예시

 

6

 

 

---

 

풀이

 

DP 문제 난이도 중하. 전체 숫자에서 i번째 index의 숫자를 n[i]이라고 할 때, 다음과 같은 상황이 있을 수 있다.

 

• n[i] = 0 : 이 경우는 해석이 불가능하다. 알파벳 기호로 암호화하려면 1에서 26 사이의 값이 나와야 하기 때문.
• 10 <= n[i]n[i+1] <= 26 : 만약 i+1번째 index에 접근 가능하며(즉 i번째 숫자가 전체 숫자의 끝이 아니며) 두 숫자를 이어붙인 값이 10에서 26인 사이라면 이를 알파벳 한 글자로 해석하는 것이 가능하다.
• n[i] > 0 : 혹은, n[i]자체가 하나의 알파벳을 가리키는 데 쓰일 수 있다.

 

즉, 위 전략에 맞추어 DP를 구성하면 빠르게 문제를 풀이할 수 있다. 

 

 

풀이 코드

MOD = 1000000
N = input().strip()
if N == '0' :
  print(0)
  exit()
N_len = len(N)
dp = [0]*(N_len + 1)
dp[0] = 1
for i in range(N_len) :
  if N[i] == '0' :
    continue
  if i < N_len - 1 and '10' <= N[i:i+2] <= '26' :
    dp[i+2] = (dp[i+2] + dp[i]) % MOD
  dp[i+1] = (dp[i+1] + dp[i]) % MOD

print(dp[-1])

풀이 완료~