2011. 암호코드 (Python)

2011번: 암호코드

 

풀이

 2차원 dp를 사용하여 문제를 해결했다. dp[n][m]의 의미는 다음과 같다.

• dp[n][m] : 입력으로 주어진 숫자의 N번째 자리의 숫자를 M 자릿수(M은 1 또는 2) 사용했을 때의 경우의 수 

 글로 풀어 쓰자니 조금 이상한데.. 예로 들면 문제의 예제처럼 25114가 입력으로 주어지고 현재 N이 4라고 생각해보자. 입력으로 주어진 숫자의 4번째 자리의 수는 1이다.

 이제 이 4번째 숫자를 한 자릿수로(M = 1) 생각하면 1에 해당하는 A 문자로 바꿀수 있고 이는 앞의 숫자인 251로 만들 수 있는 모든 문자의 뒤에 'A'를 추가하는 것이다.

 M이 2인 경우는 4번째 숫자의 앞에 있는 숫자까지 합하여 두 자릿수인 11을 만들어 생각한다. 11은 K에 해당하고 이는 앞의 숫자인 25로 만들 수 있는 모든 문자의 뒤에 'K'를 추가하는 것이다.

 

 위의 설명을 바탕으로 점화식을 만들면 다음과 같다.

• dp[n][1] = dp[n-1][1] + dp[n-1][2] (단, 숫자는 1 ~ 9에 해당되어야 한다.)
• dp[n][2] = dp[n-2][1] + dp[n-2][2] (단, 숫자는 1 ~ 26에 해당되어야 한다.)

 

 입력으로 주어진 숫자를 문자열로 생각하여 푼다면 주의할 것이 있는데 두 자릿수 숫자로 생각하여 풀 때, 문자열이기 때문에 '06'과 같이 앞에 0이 들어간 숫자가 들어올 수 있다. 그렇기 때문에 앞 자리가 '0'일 때는 분기 처리 해주어야 한다. 

 그리고 최종적으로 dp[num의 길이][1] + dp[num의 길이][2]가 문제의 정답이 되는데 둘을 합한 후에 마찬가지로 1000000으로 나눈 나머지를 출력하도록 해주어야 한다. dp를 구할 때 모두 나머지 연산을 처리해 주었는데 마지막에 출력할 때 나머지 연산을 해주지 않아서 반례를 찾느라 고생했다. 

 

 

코드

OPERAND = 1_000_000

if __name__ == '__main__':
    num = input()

    # dp[n][m] : 입력으로 주어진 숫자의 N번째 자리의 숫자를 M 자릿수(M은 1 또는 2) 사용했을 때의 경우의 수
    dp = [[0 for _ in range(3)] for _ in range(len(num) + 1)]
    dp[0][1] = 1

    for dpIdx in range(1, len(num) + 1):
        numIdx = dpIdx - 1

        oneNum = num[numIdx]  # 현재 인덱스에서 한 자릿수
        if oneNum != '0':  # '0'인 경우는 제외하고 연산
            dp[dpIdx][1] = (dp[dpIdx-1][1] + dp[dpIdx-1][2]) % OPERAND

        if numIdx == 0:
            continue

        twoNum = num[numIdx-1] + oneNum  # 현재 인덱스에서 두 자릿수
        if twoNum[0] != '0' and twoNum <= '26':  # 앞 자리가 '0'인 경우는 제외해주어야 한다.
            dp[dpIdx][2] = (dp[dpIdx-2][1] + dp[dpIdx-2][2]) % OPERAND

    # 마지막에 출력할 때도 나머지 연산을 해주어야 한다.
    print((dp[len(num)][1] + dp[len(num)][2]) % OPERAND)