📚 2011 - 암호코드

백준 사이트 : 암호 코드

문제 해결

• 최근 푼 dp 문제 중에서 점화식 구하는 데에 있어 가장 어려웠던 것 같다.
• 예외 케이스를 잘 찾아야 한다.
• 배열로 처리한다.
• dp 인덱스 i 번째를 찾을 때, i - 1, i - 2를 이용한다.

💡 문제는 두 가지 경우의 수가 존재한다.

문제에 나와있는 숫자 25114를 기준으로

idx 1
2

idx 2
25
2 - 5

idx 3
2 - 5 -1
25 - 1

idx 4
2 - 5 - 1 - 1
25 - 1 - 1
25-11
2-5-11

idx 5
2 - 5 - 1 - 1 - 4
2 - 5 - 11 - 4
25 - 11 - 4
25 - 1 - 1 - 4
2 - 5 - 1 - 14
25 - 1 - 14

• idx 3를 보았을 때
  ➡️ 5와 1을 합칠 수 없어, 사이에 -가 들어가 있다. (범위가 26이하이니)

• idx 4를 보았을 때
  ➡️ dp[idx3]꺼 뒤에 - arr[4] : 1이 추가된 것을 확인할 수 있다.
  ➡️ dp[idx2]꺼 뒤에다가 - arr[3]과 arr[4]를 합친 것이 추가된 것을 확인할 수 있다.

• idx 5를 보았을 때
  ➡️ dp[idx4]꺼 뒤에 - arr[5] : 4가 추가된 것을 확인할 수 있다.
  ➡️ dp[idx3]꺼 뒤에 - arr[4]와 arr[5]를 합친 것이 추가된 것을 확인할 수 있다.

🔔 규칙

• arr[idx - 1] * 10 + arr[idx]가 10과 26사이에 있는 값일 때 : dp[idx] += dp[idx - 1] + dp[idx - 2]
• arr[idx - 1]가 1과 9사이에 있는 값일 때 : dp[idx] += dp[idx - 1]
  • 두 개의 식을 보면 dp[idx - 1]가 추가된다.
• 주의할 것이 첫 시작 값이 0이 아닐 때 위 식이 적용된다는 것이다.

소스

import sys

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

dp = [0] * (len(pw) + 1)

if pw[0] == 0:
    print("0")

else:
    pw = [0] + pw
    dp[0] = dp[1] = 1
    for idx in range(2, len(pw)):
        # 중간에 0이 있으면 이전 결과를 그대로 가져와야한다.
        if pw[idx] >= 1:
            dp[idx] += dp[idx - 1]
        # print("현재")
        if 10 <= pw[idx - 1] * 10 + pw[idx] <= 26:
            dp[idx] += dp[idx - 2]
            # print("idx 가", idx, "pw [", idx - 1, "] : ", pw[idx - 1], "pw [", idx, "] : ", pw[idx], "dp[idx - 1] : ",
            #       dp[idx - 1], "dp[idx] : ", dp[idx])

    print(dp[len(pw) - 1] % 1000000)

😨 그리고....

• 문제에서 제시한 예외 상황을 잘 확인하고 코드를 작성해야 한다.
• 힌트를 찾으니 '아 이렇게 풀어야 겠다' 라고 쉽게 생각했지만, 문제에서 제시한 조건을 처리하는데 시간이 많이 걸렸다.

채점 결과

참고

• https://jyeonnyang2.tistory.com/55