[백준2011번] 암호코드 / Python3

문제

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

• 상근: 그냥 간단히 암호화 하자. 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

나의 풀이

이 문제는 앞에서부터 한 자리와 인접하는 두 자리의 숫자(1~26사이의 숫자)를 확인하면서 가능한 개수를 세어나가야하는 문제이다. 사용할 dp의 구조는 행으로 입력으로 주어지는 숫자의 길이로 각 i번째 숫자에서 i번째 숫자 한 자리인 경우와 i-1번째부터 i번째 자리까지 두 자리인 경우를 확인한다. 따라서 두 경우이므로 열에는 2개의 경우에서 각각의 경우의 수를 저장한다. 따라서 dp의 사이즈는 dp[숫자의 길이+1][2]가 될것이다.

이제 dp를 어떠한 방식으로 구해나갈지 구조를 정하였으니 로직을 짜야한다. 우선 맨 첫자리에 대하여 초기값을 정해야한다. 따라서 맨 앞자리의 숫자를 확인해서 dp[1][0]을 증가시켜주어야 한다. 왜 확인을 해야할까? 이 문제에서 암호가 될 수있는 수는 A인 1부터이다. 그렇기때문에 맨앞에 0이 온다면 해석을 할 수 없는 경우에 해당하는 것이다. 따라서 맨처음 값이 0인지를 확인해야하는 것이다. 그리고 중요한 점은 dp[0][0]도 1로 초기화를 해주어야한다는 것이다. 이는 i가 2일때를 볼때 설명할 수 있다. 그럼 i가 2일 경우를 보자. i가 2일때부터는 두 경우를 확인해야한다. 1. 두 번째 한 자리 수, 2. 첫 번째와 두 번째자리를 합친 수이다. 1번의 경우에는 바로 이전 i값에서의 모든 경우의 수를 저장해준다. 2번의 경우는 첫 번째와 두 번째자리가 합쳐진 수가 알파벳 범위인 10이상 26이하인지를 확인해주고 현재 i의 전의 전 경우의 수를 저장해준다. 이것 때문에 dp[0][0]을 1로 저장해준 것이다. i가 2라면 i-2는 0인데 이 값이 0이라면 2번의 경우가 아무리 참이라해도 0만 주구장창 저장이 될 것이기 때문이다. 이렇게 i가 2일때부터는 반복을 해주면 된다. 좀 더 설명을 위해 25114에서의 경우를 예로들어보겠다.

점화식을 써보자면 다음과 같다.

1. dp[i][1] = dp[i-1][1] + dp[i-1][2]        (if code[i] > 0)
2. dp[i][2] = dp[i-2][1] + dp[i-2][2]   (if 10 <= codi[i-1:i+1] <= 26)

이렇게 dp를 구하고나면 가장 마지막 i값에서의 1과 2의 경우의 수를 더해주면 답이 된다. 위 점화식에서의 조건이 성립할 경우에만 경우의 수를 바꿔주기 때문에 해독이 불가능하다면 자연스럽게 답은 0이 나올 것이고 그렇지 않다면 제대로 된 경우의 수가 나올 것이다.

코드

# 2011번 암호코드

# main
code = input()

dp = [[0 for _ in range(2)] for _ in range(len(code)+1)]

if int(code[0]) == 0:
    print(0)
else:
    dp[0][0] = 1    # 처음 두 자리로 가능할 경우
    dp[1][0] = 1    # 맨 앞으로 가능한 개수

    # dinamic programming
    for i in range(2, len(code)+1):

        # 한 자리 수의 경우
        if int(code[i-1]) > 0:
            dp[i][0] = sum(dp[i-1]) % 1000000

        # 두 자리 수의 경우
        if 10 <= int(code[i-2:i]) <= 26:
            dp[i][1] = sum(dp[i-2]) % 1000000

    print(sum(dp[-1]) % 1000000)