[ BOJ ] 2591 : 숫자카드 ( GOLD 5 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/2591)

문제

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.

나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.

카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫 줄에 카드의 숫자를 차례로 적어 놓은 것이 주어지며, 이것은 최대 40자 이하의 숫자로 이루어진다.

출력

첫 줄에 가능한 카드 배열이 몇 개인지를 출력한다.

풀이 과정

DP를 사용해 풀이했다.

dp[i] = 카드의 숫자를 i번째까지 만들었을 때 가능한 카드 배열 개수

 

1부터 9까지의 1자리 숫자 카드를 사용할 때

-- 0이 나온 경우는 10이나 20, 30 으로 만들어야 하는 숫자이므로 제외한다.

10부터 34까지의 2자리 숫자 카드를 사용할 때

-- 2자리를 커버할 때 해당 숫자의 범위가 10과 34 사이인지를 확인한다.

import sys
input = sys.stdin.readline

string = list(input().rstrip())
dp = [0 for _ in range(len(string)+1)]
dp[0] = 1

for i in range(1, len(string)+1):
    # 2자리 사용
    if i >= 2:
        if 10 <= int(string[i-2] + string[i-1]) <= 34:
            dp[i] += dp[i-2]

    # 1자리 사용
    if string[i-1] != '0':
        dp[i] += dp[i-1]
        
print(dp[-1])