백준 2011번 : 암호코드 파이썬/Python - DP

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

2011번: 암호코드

암호해석 가능한 것은 두가지 경우가 있다 
현재 인덱스에 해당하는 숫자를 한 숫자로 볼것인지 or 한칸 앞의 숫자와 합해서 두자리숫자로 볼것인지이다. 

dp[i] 에는 i 번째 숫자까지의 해석이 x개가 있다면 x개 값을 저장한다. 문제에서도 아주 큰 값이 나올 수 있다고 광고를 하고 있으니 dp가 좋은 해결방법이라고 생각했다 

i) 현재 확인중인 인덱스에 해당하는 숫자를 한자리 수로 해석 

2 5 1 1 4 라는 암호가 주어졌을 때 
예를들어 모든 자리를 한자리 숫자로 본다면 2 / 5 / 1 / 1 / 4라고 할 수 있을 것이다. 

 

if int(data[i - 1]) > 0:  # 1~ 9
    dp[i] += dp[i - 1]  # 2 / 4/ 1/ 1/ 4 -> 1가지

 

ii) 현재 확인중인 인덱스를 일의 자리숫자, 인덱스 한칸 앞의 숫자를 십의 자리라고 보고 두자리수로 해석 

25 / 11 / 4 , 2 / 5/ 1 / 14 ..이런 경우들이 있을 것이다. 문제에서 A ~ Z가 1 ~ 26라고 했으며, 일의자리는 위의 if문에서 확인중이니 10 ~ 26를 범위로 설정했다. 

if 10 <= int(data[i - 2]) * 10 + int(data[i - 1]) <= 26:  # 두자리수가 1 ~ 26 이면 25/11/4 이런식으로 나눌 수 있음
    dp[i] += dp[i - 2]

iii) 또한 암호가 무조건 틀릴 수 밖에 없는 경우가 있다. 
-> 0번째 인덱스가 '0' 이면 틀리다. 
-> 다른 인덱스에 '0' 이 들어간다면 202010 은 20, 20, 10 과 같이 두자리수로 해석가능하므로 틀린 암호는 아니다 
-> 30, 40.. 의 경우

10 <= int(data[i - 2]) * 10 + int(data[i - 1]) <= 26

조건절에서 걸러진다. 

 

전체 코드

data = input()
n = len(data)
dp = [0] * (n+1)

dp[0] = 1 # 25 를 저장하기 위해서
dp[1] = 1
flag = True
if data[0] == '0': # 암호가 틀릴 수 밖에 없는 경우이다 0번쨰 인덱스에 0이면 틀리다 다른 인덱스에는 0이 들어가도 10,20 같은 경우가 있음
    flag = False    # 30 , 40 .. 의 경우에는 15번째 줄에서 걸러지게 됨 
for i in range(2, n + 1):
    if int(data[i - 1]) > 0:  # 1~ 9
        dp[i] += dp[i - 1]  # 2 / 4/ 1/ 1/ 4 -> 1가지

    if 10 <= int(data[i - 2]) * 10 + int(data[i - 1]) <= 26:  # 두자리수가 1 ~ 26 이면 25/11/4 이런식으로 나눌 수 있음
        dp[i] += dp[i - 2]


if flag:
    print(dp[n]%1000000)
else:
    print(0)