https://acmicpc.net/problem/2591

풀이

#dp
카드를 만들 수 있는 경우가 한 자리 수로 만드는 경우에는 1~9 / 두자리 수로 만드는 경우에는 10~34로 만들 수 있다.
dp[i]에 i번째 숫자로 한자리수를 만드는 경우와 i-1번째 숫자와 i번째 숫자를 연결해서 두자리 수를 만드는 경우를 더해주었다.
그런데 이때 고려해주어야 할 부분이
1. 두자리수를 만들었을 때 범위를 초과하는 경우(34 초과) -> 두자리 수 못 만듦
2. i-1번째 수가 0인 경우 -> 두자리 수 못 만듦
3. i번째 수가 0인 경우 -> 한자리 수 못 만듦
이 있다.
그래서 이 부분을 if / elif / else 문으로 조건을 나눠서 구현해주었다.

코드

# 0 카드가 없다는 점을 생각해주지 못해서 처음에 틀렸어서 고쳤음
# 숫자 범위가 유효하다면 앞자리와 이어서 + 독립 하게 만들수 있으므로 dp[i-1]+dp[i-2]
# 숫자 카드가 이어진 경우 34를 초과하거나, 앞자리가 0인 경우에는 독립 카드로만 dp[i-1]
# 현재 숫자 카드가 0인 경우에는 무조건 앞과 이어주어야 한다. dp[i-2]

nums = input()
dp = [0]*(len(nums))

dp[0] = 1
if len(nums)>=2:
    if nums[1]!='0' and nums[0]+nums[1] <= '34':
        dp[1] = 2
    else:
        dp[1] = dp[0]

if len(nums)>=3:
    for i in range(2, len(nums)):
        # 두가지 다 가능한 경우
        if nums[i-1]!='0' and nums[i]!='0' and nums[i-1]+nums[i] <= '34':
            dp[i] = dp[i-1]+dp[i-2]
        # 이전이 0이거나 34 초과하는데 현재 숫자가 0이 아닌 경우 -> 독립으로 사용
        elif nums[i] != '0':
            dp[i] = dp[i-1]
        # 현재 숫자가 0인 경우 -> 이어서 사용
        else:
            dp[i] = dp[i-2]

print(dp[len(nums)-1])