[백준] 암호 코드 2011번 (python) DP

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

 

풀이 방법

암호를 해독하는 방법에는 한 글자씩 하거나 두 글자를 묶는 경우 2가지 경우가 존재한다.

DP알고리즘에서 dp[i]를 i번째 까지 가능한 경우의 수라고 가정한다면 만약 한 글자씩 끊어서 하는 경우라면 dp[i-1]의 경우의 수를 더해주면 된다. 만약 i-1번째 수와 i번 째 수를 묶는다고 가정하면 이때 경우의 수는 i-2번째 경우의 수와 같으므로 해당하는 경우의 수를 더해주면 된다. 

 

dp의 인덱스를 i를 i번째 까지 가능한 수라고 한다면 dp[1]일 때 i-2는 -1 이 되므로 예상치 못한 결과가 나오게 된다. 그러므로 인덱스를 하나씩 +1 해서 i+1이 i번째 까지 가능한 경우의 수라고 했다.

 

n = list(map(int,input()))
l = len(n)
dp = [0 for _ in range(l+2)]
if (n[0] == 0) :
    print("0")
else :
    dp[0], dp[1] = 1, 1
    for i in range(1, l):
        if n[i] > 0:
            dp[i+1] += dp[i]
        temp = n[i-1] * 10 + n[i]
        if temp >= 10 and temp <= 26 :
            dp[i+1] += dp[i-1]
    print(dp[l] % 1000000)