백준 2011 암호코드

과정

• dp문제
• 입력받은 배열을 순회하면서 현재 위치까지 가능한 경우의 수를 dp에 저장하기
• 예외, 반례를 많이 생각해야하는 문제
• 암호가 되지 않는 경우는 0을 출력해야한다.

• 맨 앞 자리에 0이 오면 불가능한 암호
• 한 자리 암호가 있을 수 있고, 10~26은 두 자리 암호가 될 수 있다.
  • 1~9 는 한 자리 암호가 가능하다
  • 앞 자리와 현재 자리, 두 자리 수가 10~26이면 두 자리 수가 가능하다
    • 10, 20인 경우, 한 자리 암호는 불가능하고, 두 자리 암호만 가능하다

• 0 때문에 예외 생각하기 까다로웠던 문제

map_lst = list(map(int, input()))

length = len(map_lst)

dp = [0] * length

if length == 0:
    print(0)

else:
    for i in range(length):

        if i == 0:
            if 1 <= map_lst[0] < 10:  # 맨 앞 숫자 보고 0 또는 1
                dp[0] = 1
            else:
                break

        elif i == 1:  # 1번째 숫자 정하기
            if map_lst[i] == 0:
                if 10 <= map_lst[i - 1] * 10 + map_lst[i] <= 20:
                    dp[i] = 1
                else:
                    dp[i] = 0
                    dp[i - 1] = 0

            elif 10 < map_lst[i - 1] * 10 + map_lst[i] <= 26:
                dp[i] = 2

            else:
                dp[i] = 1

        elif map_lst[i - 1] * 10 + map_lst[i] == 0:  # 00 인 경우
            dp[i - 1] = 0
            dp[i] = 0

        # 예외 아닌 경우 상시 적용
        
        elif map_lst[i] == 0:
            if map_lst[i - 1] * 10 + map_lst[i] <= 20:
                dp[i] = dp[i - 2]
            else:
                dp[i] = 0
                dp[i - 1] = 0

        elif 10 < map_lst[i - 1] * 10 + map_lst[i] <= 26:
            dp[i] = dp[i - 2] + dp[i - 1]

        else:
            dp[i] = dp[i - 1]

    print(dp[-1] % 1000000)

• 감사하게도 반례를 모아주셨다.
  https://www.acmicpc.net/board/view/52607

• 예외를 못 찾은 흔적...