백준 2011 암호코드 (파이썬)

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

 

제출 코드

def solve():
    code = list(map(int, input()))
    dp = [0] * (len(code)+1)
    dp[0] = 1
    dp[1] = 1
    if code[0] == 0:
        print(0)
        return
    N = len(code)
    code = [0] + code
    for i in range(2, N+1):
        one = code[i]
        if one > 0:
            dp[i] += dp[i-1]
        two = code[i-1]*10 + code[i]
        if 10 <= two <= 26:
            dp[i] += dp[i-2]

    print(dp[N]%1000000)
    #print(dp)

if __name__ == "__main__":
    solve()

 

후기

너무 어렵습니다.. 다시 풀었는데 안풀려서 결국 검색했는데 검색하고 답을 이해하는데도 시간이 오래 걸렸습니다.

일단 처음에 0이 나오면 어떤 경우에서든 암호가 잘못된 경우로 해독을 할 수 없습니다. 그래서 0을 출력하고 강제 종료했습니다.

그 다음 dp는 한 자리를 선택하는 경우와 연속 2개를 선택하는경우로 나누어 풀어야 합니다,

먼저 한 자리를 선택한 경우, 그 수가 10보다 작으면 dp[i-1] 를 더해줍니다.

한 자리 선택한 경우 연속된 다음 자리를 선택한 경우가 10이상 26이하이면 현재 dp에 dp[i-2]를 더해줍니다.

이 후는 1000000을 나머지 연산으로 출력하기만 하면 됩니다.

 

제가 참조한 사이트는 여기입니다.

https://archive-me-0329.tistory.com/23?category=965963 

엄청 자세하게 설명해주셔서 도움이 많이 되었습니다.

 

저는 DP가 아직도 감이 안 잡히고 계속 겁이 나네요.. 하지만 계속 반복적으로 DP만 풀어서 꼭 DP를 정복하겠습니다.