[Python - Dynamic Programming] 2011 암호코드

📌 문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

📌 입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

📌 출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

 

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

📌 문제 풀이

👨‍🏫 접근

진짜 며칠을 고민했던 것 같다. 이렇게 풀면 저게 문제고, 저렇게 풀면 이게 문제고..

 

일단 가장 고통받았던 것은 0의 존재이다.

아무리 잘 풀어도 0 때문에 틀린 경우가 많았다. 예를 들어, 10은 1, 1010은 1, 100은 0, 001은 0,10010도 0이었다.

 

그래서 예외 처리가 조금 까다로웠던 문제다. 이 문제는 미리 특정 문자열의 경우의 수를 저장해 놓으면 계속해서 사용하면서 시간복잡도를 줄일 수 있어서 DP로 푸는 문제이다. 보통 이렇게 문자열을 주제로 최대-최소, 가능한 수 등을 구하라고 하는 문제는 대개 DP로 푼다.

 

DP는 재귀와 함께 구현했다. 먼저 DP에서 n번 인덱스에서 n + 1번 인덱스와 n + 2번 인덱스로 넘어가면서 재귀를 구현했다. 의사코드로 설명하면 아래와 같다.

def 재귀(인덱스):
	d[인덱스] += 재귀(인덱스 + 1)
    d[인덱스] += 재귀(인덱스 + 2)

이렇게 작성한 이유는 각 암호는 1~26까지만 치환이 되고 세 자리수를 넘어가지 않기 때문이다. 입력 예제인 "25114"로 생각하면 "2 / 5114", "25 / 114" 인 것이다. 그리고 재귀 DP가 통상 그러하듯 아래와 같은 조건을 세워줬다.

if 인덱스가 배열의 길이보다 크다면:
	return 1

if dp테이블에 값이 있다면:
	return dp[인덱스]

인덱스가 배열을 넘어가는 것은 아무 문제 없이 순회를 마쳤다는 반증이다. 그리고 값이 있으면 시간 복잡도를 줄이기 위해 연산을 다시 하지 않고 테이블 값을 불러온다.

 

여기서 중요한 것은 0과 26을 넘어가는 수를 어떻게 처리할 것이냐이다. 진짜 개짜증난다. 하지만 풀이 방법은 있다.

일단 순회를 하면서 배열 인덱스 값을 찾아서 그 값이 0일 때와 0이 아닐 때로 경우를 구분한다.

 

1. 0이 아닐 경우

크게 문제되지 않아서 평소대로 처리해주면 된다. 다만, 26을 넘어가는 것은 예외로 처리해준다.

 

먼저 한 자리수만 검사하는 경우다.

현재의 인덱스에서 다음 인덱스로 넘어가서 검사를 해준다. 예를 들어, 25114에서 0번 인덱스인 2에서 나머지 5114를 검사하고, 1번 인덱스인 5에서는 나머지 114를 검사하는 식으로 넘어가는 것이다.

 if 0이 아니면:
 	d[인덱스] += 재귀(인덱스 + 1)

그 다음 두 자리 수를 검사한다.

이 경우에는 이 두 자리 수가 26을 넘어가나 안 넘어가나 검사하는 것이 관건이다. 25114에서 가운데에 있는 51은 복호화할 수 없다. 왜냐하면 26까지 Z로 치환하고 그를 넘어서면 불가능하기 때문이다. 그리고 또 중요한 것은 IndexError가 발생하지 않도록 l을 넘지않는 선에서 검사하는 것이다.

if 인덱스 + 1 <= 배열 길이:
	if int(arr[인덱스:인덱스 + 1])이 26보다 작거나 같다면:
    	d[인덱스] += 재귀(인덱스 + 2)

그래서 조건을 만족하면 인덱스  + 2 값으로 이동하여 검사한다. 25114에서 25 다음에 114를 검사하기 시작하는 경우다.

 

2. 0인 경우

0인 경우가 문제인데, 의외로 간단하게 처리할 수 있다. 일단 0을 포함하여 복호화할 수 있는 것은 10과 20의 경우밖에 없다. 그렇지 않고 01 혹은 09 등은 모두 복호화할 수 없는 것이다.

2-1. 01~09의 경우

이 경우는 맨 처음에 배열의 i번째 인덱스 값이 0인지 아닌지로 검사한다.

만약 그 값이 0이라면 불가능한 경우이기 때문에 0을 리턴해준다.

if 0이 아닌 경우:
	...
else:
	return 0

이것이 가능한 이유는 10, 20에서 0번 인덱스(1, 2)를 검사하고 1번 인덱스(0) 값을 검사할 때, 1번 인덱스 값 검사는 0이기 때문에 0을 리턴하며, 두 자리 수 연산에서 이를 처리하기 때문이다. 자세한 내용은 아래의 경우에서 확인할 수 있다.

2-2. 10, 20의 경우

이 경우에는 사실 0을 건너뛴다. if int(arr[i:i + 2])  <= 26 을 만족시키기 때문에 d[i]를 구할 때, 인덱스  + 2로 넘어가서 "10"에서 "1"의 다음 다음 인덱스부터 검사를 시작한다. 따라서 정리하자면, 아래와 같이 코드를 작성할 수 있다.

if arr[i] != "0":
    d[i] += encrypt(i + 1) % div
    if i + 1 <= l:
        if int(arr[i:i + 2]) <= 26:
            d[i] += encrypt(i + 2) % div
else:
    return 0

그런데 여기서 encryp(i + 1)이 배열의 길이를 넘어가는 경우가 발생한다. 이 경우를 대비하여 위에서 인덱스가 배열의 길이를 넘어가는 경우 1을 리턴하기로 한 것이다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
sys.setrecursionlimit(10**6)
div = 1000000

arr = sys.stdin.readline().rstrip()
l = len(arr) - 1
d = [0] * (l + 1)


def encrypt(i):
    if i > l:
        return 1

    if d[i] != 0:
        return d[i]

    if arr[i] != "0":
        d[i] += encrypt(i + 1) % div
        if i + 1 <= l:
            if int(arr[i:i + 2]) <= 26:
                d[i] += encrypt(i + 2) % div
    else:
        return 0

    return d[i] % div


print(encrypt(0))

📄 준비

import sys
sys.setrecursionlimit(10**6)
div = 1000000

arr = sys.stdin.readline().rstrip()
l = len(arr) - 1
d = [0] * (l + 1)

값이 커질 수 있기 때문에 10**7로 나눈 나머지를 연산해준다. 수를 작게 해줄 뿐더러 복잡도도 줄어든다.

📄 풀이

def encrypt(i):
    if i > l:
        return 1

    if d[i] != 0:
        return d[i]

    if arr[i] != "0":
        d[i] += encrypt(i + 1) % div
        if i + 1 <= l:
            if int(arr[i:i + 2]) <= 26:
                d[i] += encrypt(i + 2) % div
    else:
        return 0

    return d[i] % div


print(encrypt(0))

📌 총평

극혐문제...