[DP] 백준 2011번 “암호코드” Python 풀이

문제 링크

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

풀이

• 마지막 숫자까지 해석할 수 있는 경우의 수는 아래 두 가지 경우의 수의 합과 같습니다.
  • 마지막 1개 숫자 이전의 숫자들로 가능했던 경우의 수
  • 마지막 2개 숫자 이전의 숫자들로 가능했던 경우의 수
• 따라서, “251”을 해석할 수 있는 경우의 수는 아래 두가지 경우의 수의 합과 같습니다.
  • “마지막 1개 숫자 이전의 숫자들로 가능했던 조합” + “1”
    • 즉, “25”의 경우의 수와 동일합니다.
    • 마지막 1개의 숫자가 0 이상이기 때문에 가능합니다.
  • “마지막 2개 숫자 이전의 숫자들로 가능했던 조합” + “51”
    • 즉, “2”의 경우의 수와 동일합니다.
    • 해당 경우엔 마지막 2개의 숫자가 10 이상 26 이하가 아니기 때문에 불가능합니다.
• 다음으로, “2511”을 해석할 수 있는 경우의 수는 아래 두 가지 경우의 수의 합과 같습니다.
  • “마지막 1개 숫자 이전의 숫자들로 가능했던 조합” + “1”
    • 즉, “251”의 경우의 수와 동일합니다.
    • 마지막 1개의 숫자가 0 이상이기 때문에 가능합니다.
  • “마지막 2개 숫자 이전의 숫자들로 가능했던 조합” + “11”
    • 즉, “25”의 경우의 수와 동일합니다.
    • 마지막 2개의 숫자가 10 이상 26 이하이기 때문에 가능합니다.
• 마지막으로, “25114”를 해석할 수 있는 경우의 수는 아래 두 가지 경우의 수의 합과 같습니다.
  • “마지막 1개 숫자 이전의 숫자들로 가능했던 조합” + “4”
    • 즉, “2511”의 경우의 수와 동일합니다.
    • 마지막 1개의 숫자가 0 이상이기 때문에 가능합니다.
  • “마지막 2개 숫자 이전의 숫자들로 가능했던 조합” + “14”
    • 즉, “251”의 경우의 수와 동일합니다.
    • 마지막 2개의 숫자가 10 이상 26 이하이기 때문에 가능합니다.

코드

import sys

number = list(map(int, sys.stdin.readline().rstrip()))

# dp[i] => i번째 숫자까지 해석할 수 있는 경우의 수
dp = [0] * (len(number)+1)
dp[0] = 1
dp[1] = 1 # 1번째 숫자까지 해석할 수 있는 경우의 수는 1이므로 미리 계산

# 암호가 잘못되어 해석할 수 없는 경우 (첫 번째 숫자가 0일 경우)
if (number[0] == 0):
    print(0)
else:
    for i in range(1, len(number)):

        # dp[0]이 사용되고 있으므로 dp 접근용 idx 재선언
        j = i+1

        if (number[i] > 0):     # 마지막 1개의 숫자가 0이면 대응되는 문자가 없음
            dp[j] += dp[j-1]    # 마지막 1개 숫자 이전의 숫자들로 가능했던 경우의 수와 동일하기 때문에, 해당 경우의 수를 더해주기

        if (10 <= 10 * number[i-1] + number[i] <= 26): # 마지막 2개의 숫자가 10 이상 26 이하라면
            dp[j] += dp[j-2]    # 마지막 2개 숫자 이전의 숫자들로 가능했던 경우의 수와 동일하기 때문에, 해당 경우의 수를 더해주기

    print(dp[-1]%1000000)

참고

• https://velog.io/@jxlhe46/백준-2293번.-동전-1-bfi120m5