[BOJ/백준] 2011번 암호코드 (Python 파이썬)

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

2011번: 암호코드

 

문제

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

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

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

입력

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

출력

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

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

예제 입력 1 

25114

예제 출력 1 

6

예제 입력 2 

1111111111

예제 출력 2 

89

 

---

풀이

일단 문제를 이해하기 위해 정리해 보겠습니다.

상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?

이 말은 25114을 다음과 같이 해석했음을 의미합니다.
2, 5, 1, 1, 4
25, 1, 1, 4
25, 11, 4
2, 5, 11, 4
2, 5, 1, 14

즉, 띄어쓰기에 따라서 다양하게 해석될 수 있는 것이죠.

이제 해석의 기준을 정해야 합니다. 우선 1자리수와 2자리수로 나눌 수 있겠습니다.

문제에서 A는 1번부터이니, 1자리수는 "0보다 크고 9보다 작거나 같다"을 확인하면 됩니다.
알파벳이 26개이므로, 2자리수는 "10보다 크거나 같고 26보다 작거나 같다"을 확인하면 됩니다.

이제, 개수를 구해 보겠습니다

역시나 dp 리스트를 선언 후, 밑에서부터 올라가면서 계산하겠습니다.

간단하게 25114 중에서 "251"에 대해서 경우의 수를 구해봅시다.

2/5/1,  25/1 이렇게 두 개만 가능합니다.

이제 "2511"을 계산하기 위해서 "251"에 1을 붙인다고 생각해 봅시다.

1. 1자리수로 붙는 경우
   위에서 정리했듯이 0보다 크기만 한다면 1자리수로 붙일 수 있습니다.
   그렇다면, "251"에 1을 붙이는 것이므로, "251"을 만드는 경우의 수와 동일하게 경우의 수가 나오게 됩니다.
   => 2/5/1/1, 25/1/1
2. 2자리수로 붙는 경우
   이제는 앞에 있는 1과 합쳐서 11을 만들고 이것이 26보다 작은지 검사합니다. (true)
   그렇다면 "25" 에 11을 붙이는 것이므로, "25"을 만드는 경우의 수와 동일할 것입니다.
   => 2/5/11, 25/11

따라서 아래와 같이 점화식을 세울 수 있습니다.

        if data[k] > 0:
            dp[i] += dp[i-1]
        if 10 <= data[k] + data[k-1]*10 <= 26:  
            dp[i] += dp[i-2]

 

아래는 최종적으로 구현한 코드입니다.

Code

from sys import stdin

input = stdin.readline
data = list(map(int, input().rstrip()))
len = len(data)

dp = [0] * (len + 1)
dp[0] = 1  # 1번 인덱스의 1자리수 경우 구할 때 필요
dp[1] = 1

if data[0] == 0:
    print(0)
else:
    for k in range(1, len):
        i = k + 1  # dp용 인덱스
        if data[k] > 0:  # 1자리 허용
            dp[i] += dp[i-1]
        if 10 <= data[k] + data[k-1]*10 <= 26:  # 2자리 허용, dp[i-1]이 0일 수도 있다.
            dp[i] += dp[i-2]
    print(dp[len] % 1000000)