2591 - 해결

 

숫자카드

 

문제

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 

이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 

숫자를 차례로 적으면 27123이 된다.

 

나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 

예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.

 

카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 

가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

---

처음에는 재귀로 풀어서하였지만 시간 초과가 발생하였다.

그래서 알고르즘을 확인해보니 dp 문제였다.

import sys

card_num = list(sys.stdin.readline().rstrip())
cnt = 0
def sol(card_num):
    global cnt
    if not card_num:
        cnt += 1
        return
    
    if len(card_num) > 1 and 1 <= int("".join(card_num[:2])) <= 34:
            sol(card_num[2:])
    sol(card_num[1:])
    

sol(card_num)

print(cnt)

재귀로 풀었던 것이기 때문에 dp 문제를 구현하는것은 크게 어렵진 않았는데 dp를 생각하는게 조금 어려웠다.

그리고 처음에는 0이있는걸 신경을 안썼는데 반례를 보니 0이 있다는 것을 알아서 0이 있을 경우에는 건너뛰게하였다.

import sys
card_num = list(sys.stdin.readline().rstrip())

# 전체 길이
num_len = len(card_num)

# dp는 마지막 단계를 위해서 1개더
dp = [0] * (num_len + 1)
dp[0] = 1

for i in range(num_len):
    # 0일때는 제외
    if int(card_num[i]) ==  0:
        continue
    # 0을 제외한 모든 1자리 수는 분리가 가능하기 때문에 전의 dp와 해당 dp를 더한 값을 저장.
    dp[i+1] = dp[i+1] + dp[i]
    # 마지막 전에는 1자리밖에 없으니 할 필요가 없고 2자리가 1~34사이인지 확인.
    if i < num_len - 1 and 1 <= int("".join(card_num[i:i+2])) <= 34:
        dp[i+2] = dp[i+2] + dp[i]

print(dp[-1])