[파이썬] 백준 2011 : 암호코드 (골드5)

[파이썬] 백준 2011 : 암호코드 (골드5)

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

---

풀이

방향성 생각

• 바텀업으로 state 나눠서 전 노드/전전 노드에서 들어오는 방식으로 풀기
• 탑다운으로 조건에 맞는 경우에만 탐색 진행하기

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)

string = input()
L = len(string)

dp = [-1]*L
MOD = 1000000

def dfs(x):

    if x == L:
        return 1

    if dp[x] != -1:
        return dp[x]

    result = 0

    if string[x] != '0':
        result += dfs(x+1)

    if x+1 < len(string) and '10' <= string[x:x+2] <= '26':
        result += dfs(x+2)

    dp[x] = result%MOD

    return dp[x]

print(dfs(0))

코멘트

• .탑다운 : 종료조건 + 메모제이션 + 탐색조건 + DP 업데이트