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

2011번: 암호코드

POINT

DP

암호는 두 자리로 묶을 수 있는 수가 있으면 경우의 수가 증가한다. 자릿수가 늘어나면서 동일한 방법으로 가짓수를 구하고 앞 자리의 결과가 뒤의 자리에도 영향을 미치니까 DP(Dynamic Programing, 다이나믹 프로그래밍)으로 문제를 해결한다.

index	0	1 (시작)	2	3	4	5
code	0	2	5	1	1	4
dp	1	1	2	2	4	6

현재 자리를 i라고 하면, 다음과 같은 규칙이 생긴다.

뒤의 두 자리가 암호 범위에 속할 경우 dp[i] = dp[i - 1] + dp[i -2]

속하지 않을 경우, dp[i] = dp[i - 1]

 

암호 해독 불가

1. 0으로 시작하는 경우 (0, 001)
2. 0으로 끝나고 앞자리가 0이거나 2보다 큰 경우 (30, 80, 100)

풀이

code = list(map(int, input())) # 정수로 변환
code.insert(0, 0) # 인덱스 1부터 시작
dp = [0] * len(code)

# 0으로 시작하면 해독 불가
if code[1] == 0:
    print(0)
else:
    dp[0] = dp[1] = 1
    for i in range(2, len(code)):
        # 뒤의 두 자리가 0으로 끝나고 암호 범위를 벗어나면 해독 불가 (예: 30, 50, 100)
        if code[i] == 0 and (code[i-1] > 2 or code[i-1] == 0):
            print(0)
            exit()
        # 현재 자리가 0이 아닐 때
        if code[i] != 0:
            dp[i] += dp[i-1]
        # 뒤의 두 자리가 암호 범위에 속할 때 (예: 24, 13)
        if 10 <= code[i-1] * 10 + code[i] <= 26:
            dp[i] += dp[i-2]

    print(dp[-1] % 1000000)