🥚문제

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

• 다이나믹 프로그래밍

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

nums = [' '] + list(input().strip())
dp = [0]*len(nums)
dp[0] = 1

valid = True

for i in range(1, len(nums)):
    if i == 1:
        if nums[1] == '0':
            valid = False
            break
        else:
            dp[1] = 1
        continue

    if 10 <= int(nums[i-1] + nums[i]) <= 26:
        if nums[i] == '0':
            dp[i] = dp[i-2]
        else:
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000
    else:
        if nums[i] == '0':
            valid = False
            break
        else:
            dp[i] = dp[i-1]

if valid:
    print(dp[-1])
else:
    print(0)

---

🧂아이디어

DP

• 0을 처리하는 과정에서 좀 생각을 해야 했지만, 난도는 그렇게 높지 않았던 문제였다.

• 입력된 암호를 nums 문자열 리스트에 저장한다.

• dp[i]는 nums[i]까지의 숫자를 확인했을 때, 암호를 해석할 수 있는 경우의 수이다.

• dp[i]의 값은 다음과 같이 정해진다.

  • int(nums[i-1] + nums[i])의 값이 10이상 26이하인 경우

    • nums[i]가 '0'이면: dp[i] = dp[i-2]
      ⭐️ 0은 단독으로 올 수 없기 때문에 항상 두 자리 수를 세트로 본다!
    • nums[i]가 '0'이 아니면: dp[i] = dp[i-1] + dp[i-2]
      • ⭐️ nums[i]를 하나의 암호로 볼 때 nums[i-1]까지의 암호를 해석하는 방법의 수인 dp[i-1] + ⭐️ nums[i-1]~nums[i]를 하나의 암호로 볼 때 nums[i-2]까지의 암호를 해석하는 방법의 수인 dp[i-2]
      • dp[i-1] + dp[i-2]를 계산해 주기 위해 dp[0] = 1로 초기화

  • int(nums[i-1] + nums[i])의 값이 10이상 26이하가 아닌 경우 (두자리로는 유효한 암호가 되지 않는 경우)

    • nums[i]가 '0'이면: invalid, 0 출력!
      e.g., 30은 유효한 암호가 아니다!
    • nums[i]가 '0'이 아니면: dp[n] = dp[n-1]
      e.g., 31은 'CA'라는 암호가 될 수 있다!

• 예시 1: 25114를 해석하는 방법의 수 (6가지)
  

• 예시 2: 121074110을 해석하는 방법의 수 (2가지)