[골드 5] 백준 2591 - 숫자카드 (파이썬)

 

https://www.acmicpc.net/problem/2591

풀이

34까지의 숫자 카드가 있을 때, 주어진 숫자 문자열 S를 한 자리 또는 두 자리 숫자로 쪼개어 카드 조합을 만드는 방법의 수를 구하는 문제이다. 단, 앞자리가 0이면 안 되고, 두 자리 수는 134 사이의 유효한 카드 번호여야 한다.

• D[i]: 문자열 S의 앞에서 i자리까지 만들 수 있는 카드 조합 수
• 점화식
  • 한 자리 수 (S[i-1])가 '0'이 아니면 D[i] += D[i-1]
  • 두 자리 수 (S[i-2:i])가 '10' ~ '34' 범위에 속하면 D[i] += D[i-2]

S = input()
D = [0] * (len(S) + 1)  # D[0] ~ D[len(S)]
D[0] = 1  # 빈 문자열은 1가지 방법 (기저 조건)

for i in range(1, len(S) + 1):
    D[i] = 0

    # 한 자리 수 확인 (0은 불가능)
    if S[i - 1] != '0':
        D[i] += D[i - 1]

    # 두 자리 수 확인
    if i >= 2 and S[i - 2] != '0' and int(S[i - 2:i]) <= 34:
        D[i] += D[i - 2]

코드

# 백준 2591 - 숫자카드
# 분류 : 다이나믹 프로그래밍

S = input()

D = [0] * (len(S) + 1)
D[0] = 1

for i in range(1, len(S) + 1) :
    D[i] = 0
    if S[i - 1] != '0' :
        D[i] += D[i - 1]
    if i >= 2 and S[i - 2] != '0' and int(S[i - 2:i]) <= 34 :
        D[i] += D[i - 2]

print(D[len(S)])