(Python) - BOJ(2011번) : 암호코드

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

2011번: 암호코드

---

• 해설 : 

알파벳을 1부터 26까지로 치환하여 숫자로만 이루어진 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

DP로 해결할 수 있는 문제이다. 1부터 9까지, 10부터 26까지 두 경우로 나누어 해석할 수 있는 가짓수를 모두 카운트한다.

 

 

 

---

• 소스코드 : 

 

a = list(map(int, list(input())))
l = len(a)
 
# dp[i] : i번째 수 단계에서 암호 코드의 개수
dp = [0] * (l+1)
 
if a[0] == 0: # 암호 만들 수 없는 경우
    print(0)
else :
    a = [0] + a # 인덱싱을 위해 추가한 0
    dp[0] = 1
    dp[1] = 1 # 첫번째 수로 이뤄진 암호코드는 1개이다.
 
    for i in range(2, l+1):
        cur = a[i] # 한 자리
        cur2 = a[i-1] * 10 + a[i] # 두 자리
        if cur >= 1 and cur <= 9:
            dp[i] += dp[i-1]
        if cur2 >= 10 and cur2 <= 26:
            dp[i] += dp[i-2]
        dp[i] %= 1000000
 
 
    print(dp[l])