[백준/2011/파이썬] 암호코드

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

2011번: 암호코드

Problem

• 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다.
• 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

조건

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

SOL

생각보다, 어려운 듯, 쉬운 문제였다. 예시로, 1,12,124 ,1249를 만들어가는 과정을 그리면서 찾으니 쉽게 규칙성을 발견할 수 있었다.

• 우선, 뒤에 새롭게 오는 숫자는,바로 앞의 경우의 수를 그대로 overlapping하게 된다.
• 이때, 새롭게 오는 숫자는 앞자리와 2자리 암호코드를 이루는지 확인을 해야한다.
  • 만약, 2자리 암호코드를 이룰 수 있다면,(10<=k<=26) 바로 앞앞의 경우의 수를 overlapping하게 된다.

위의 규칙을 그대로 식으로 나타낼 수 있다.

• DP[N] = N자리일 때, 암호코드의 경우의 수
• DP[0],DP[1] =1
• DP[i] += DP[i-1]
• if 두자리 암호코드)DP[i] += DP[i-2]

#bottom up

N = list(map(int,input()))
#print(N)
l = len(N)
# DP table도, DP[N]이 딱 답이 될 수 있도록, index를 맞춰줌.
dp = [0 for _ in range(l+1)] 
# 0으로 시작하는 경우 
if (N[0] == 0) :
    print("0")
else :
    N = [0] + N
    dp[0]=dp[1]=1
    for i in range(2, l+1):
        # 0보다 큰 수라면, 이전의 값을 그대로 가진다.
        if N[i] > 0:
            dp[i] += dp[i-1]
        #두자리 가능성을 보자.
        temp = N[i-1] * 10 + N[i] 
        if temp >= 10 and temp <= 26 :
            dp[i] += dp[i-2]
    print(dp[l] % 1000000)