Python - [백준]2011-암호코드

암호코드를 해석할 수 있는 경우의 수를 찾는 문제이다.

접근방법

1과 27 사이의 알파벳번호를 이용하여 만든 암호이다. 만약 숫자열이 주어진다면 해석하면 무엇을 만들 수 있을지 모든 경우의 숫자를 체크한다.

• 앞 한자리는 한가지의 암호밖에 만들 수 없어서 1이다.
• 두번째 숫자까지는 만약 i-1과 i의 숫자가 27보다 작으면 두가지 경우의 해석을 할 수 있고, 아니라면 그대로 한가지의 경우만 가능하다.

위의 경우를 이용하여 두가지의 조건을 세울 수 있다.

• 1. 만약 0이 아닌(암호 코드 조건 만족)수가 나온다면 dp[i] = dp[i-1]
• 2. 만약 dp[i-1]과 dp[i]를 합친게 27보다 작다면 dp[i] += dp[i-2]를 더해준다.

n = input()
len_n = len(n)
dp = [0 for i in range(len(str(n)) + 1)]

if int(n[0]) == 0:
    print(0)
else:
    n = '0'+ n
    dp[0] = 1
    dp[1] = 1
    for i in range(2, len_n + 1):
        if n[i] >= '1' and n[i] <= '9':
            dp[i] += dp[i-1]
        if n[i-1] + n[i] < '27' and n[i-1] + n[i] >= '10':
            dp[i] += dp[i-2]

    print(dp[len_n] % 1000000)