[BaekJoon] 백준 2011번 암호코드

[BaekJoon] 백준 2011번 암호코드

 

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

 

내코드

 

다이나믹 프로그래밍에 익숙하지 않아서

다이나믹 프로그래밍 문제를 찾다가 발견해서 풀었다.

즉, 다이나믹 프로그래밍 문제인 것을 알고 풀었다.

 

우선 점화식을 찾았다.

f("25114")가 25114에서 나올 수 있는 암호의 개수라고 하자.

f("25114") = f("2511") + f("251")이 된다. 

즉, f(n) = f(n[:-1]) + f(n[:-2]) 이다.

 

이렇게 금방 점화식을 찾을 수 있다.

두번째로 생각해야 할 부분은 메모이제이션이다.

시간 초과를 피하기 위해 딕셔너리를 만들어 줬다.

여기서는 f(n)에서 n의 길이가 같다면 f(n)이 같다는 특징이 있다.

즉, 길이에 따라서 f(n)의 값을 저장해주고 필요하면 가져다 쓰면 된다.

 

이 문제는 반례가 많다. 특히 0을 조심해야 한다.

왜냐하면 100, 0, 0101, 80, 1090의 경우 결과 값이 0이 되기 때문이다.

 

따라서 이에 대한 예외 처리를 해줘야 하는데 포인트는 두가지다.

1. f(n[:-1])가 성립하려면 n[-1]이 0이면 안된다는 것

2. f(n[:-2])가 성립하려면 n[-2:]가 10이상 26이하여야 한다는 점

 

이렇게 예외 처리를 해주면 풀릴 줄 알았는데

파이썬의 한가지 문제가 있었다.

 

파이썬은 재귀 깊이를 1000까지밖에 기본적으로 지원을 하지 않는다.

따라서 그 이상으로 하려면 아래와 같이 처리해야 한다는 점!

import sys
sys.setrecursionlimit(10000)

 

코드

# BaekJoon2011.py
import sys
sys.setrecursionlimit(10000)


def solution(s):
    global mem

    length = len(s)

    if length == 0 or (length == 1 and int(s) != 0):
        return 1
    elif length in mem:
        return mem[length]
    else:
        if 10 <= int(s[-2:]) <= 26 and int(s[-1]) != 0:
            tmp = solution(s[:-1]) + solution(s[:-2])
        elif (10 > int(s[-2:]) or int(s[-2:]) > 26) and int(s[-1]) != 0:
            tmp = solution(s[:-1])
        elif 10 <= int(s[-2:]) <= 26 and int(s[-1]) == 0:
            tmp = solution(s[:-2])
        else:
            tmp = 0

        if length not in mem:
            mem[length] = tmp % 1000000

        return tmp % 1000000


secret = input()
mem = {}
if len(secret) == 0 or int(secret) == 0:
    print(0)
else:
    print(solution(secret))