[Python] 백준 2011 암호코드

2011번: 암호코드

다이나믹 프로그래밍 : 한번에 이해하기 어려웠다. 왜 i - 2인덱스에 접근해야 할까. 특정한 상황이 아니면 DP[i] = DP[i - 1] 이다. 하지만 뒤에 수를 가져다 붙여서 두자리 수 and 26이하의 수를 만들 수 있다면 DP[i - 2]를 추가해주어야 한다.

i - 2에 접근하는 이유는 갖다 붙일 수 있는 상태의 수이기 때문이다. 

DP[3] (2, 5, 1), (25, 1)

DP[4] (2, 5, 1, 1), (25, 1, 1), (2, 5, 11), (25, 11) 

DP[5]는 (2, 5, 1, 1, 4), (25, 1, 1, 4), (2, 5, 11, 4), (25, 11, 4) 이렇게 DP[4]의 값에 그대로 추가하는 방법 1가지와

           (2, 5, 1, 14), (25, 1, 14) 이렇게 (DP[3]값에 그대로 추가한 방법)에 숫자를 붙이는 방법 1가지를 더해주어야 한다.

 

인덱스 2개 이전의 값을 더해주는게 핵심같다.

 

전체코드

import sys

input = sys.stdin.readline

nums = list(str(input().strip()))
dp = [0 for _ in range(len(nums) + 1)]
dp[0], dp[1] = 1, 1
if nums[0] == '0':
    print(0)
else:
    for i in range(2, len(nums) + 1):
        if int(nums[i - 1]) > 0:
            dp[i] += dp[i - 1]
        to_int = int(nums[i - 2] + nums[i - 1])
        if 10 <= to_int <= 26:
            dp[i] += dp[i - 2]
    print(dp[len(nums)] % 1000000)