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

 

DP 알고리즘에서 Top-Down 방식은 재귀호출을 사용한다고 한다. 큰 문제를 작은 문제로 나누어 푸는 방식. 그러나 python은 재귀가 오래 걸리고 메모리 초과가 날 수 있다. 그러니 python은 Bottom-Up 방식을 사용하자. 작은 문제부터 풀고 문제를 점점 크게 만들면서 푼다.

a = list(map(int, list(input())))
l = len(a)

# dp[i] : i번째 수 단계에서 암호 코드의 개수
dp = [0] * (l+1)

if a[0] == 0: # 암호 만들 수 없는 경우
    print(0)
else :
    a = [0] + a # 인덱싱을 위해 추가한 0
    dp[0] = 1
    dp[1] = 1 # 첫번째 수로 이뤄진 암호코드는 1개이다.

    for i in range(2, l+1):
        cur = a[i] # 한 자리
        cur2 = a[i-1] * 10 + a[i] # 두 자리
        if cur >= 1 and cur <= 9:
            dp[i] += dp[i-1]
        if cur2 >= 10 and cur2 <= 26:
            dp[i] += dp[i-2]
        dp[i] %= 1000000


    print(dp[l])

 

DP 멍멍이 어렵다.