[Python] boj no. 2011 : 암호코드

Problem

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

Idea

i번째 숫자를 마지막 숫자로 하는 암호 코드의 해석 개수는 i-1번째 숫자를 마지막 숫자로 하는 암호 코드의 해석 개수에 영향을 받으므로 dp 문제임을 직감했다.

dp[i]가 i번째 숫자를 마지막 숫자로 할 때의 암호 코드의 해석 개수라고 할 때, i번째 숫자는 다음과 같은 두 경우로 해석될 수 있다.

1. i번째 숫자만을 이용해 해석하는 경우
2. i번째 숫자에 i-1번째 숫자를 붙여 해석하는 경우

첫 번째 경우의 경우 i번째 숫자가 0이 아닌 경우에만 해석할 수 있고, 두 번째의 경우 i번째 숫자가 6보다 작고 i-1번째 숫자가 1 또는 2일때만 가능할 수 있다.

위 조건을 이용하여 해당 조건에 부합하는 경우 이전의 결과를 이용하는 방법으로 해결하였다.

Code

import sys

code = [-1] + list(map(int, sys.stdin.readline().rstrip()))
dp = [0 for _ in range(len(code))]

if code[1] != 0:
    dp[0] = 1
    dp[1] = 1

    for i in range(2, len(code)):
        if code[i] != 0:
            dp[i] += dp[i-1]
            
        temp = code[i-1]*10 + code[i]
        
        if 10 <= temp <= 26:
            dp[i] += dp[i-2]
                
    print(dp[-1]%1000000)

else:
    print(0)

Comment