[Python] 백준 2591번: 숫자카드

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

2591번: 숫자카드

1. 카드는 1부터 34까지 있으므로 dp[숫자의길이][34]로 만들어준다.

2. 전의수 * 10 + 현재수 <= 34 성립하면 dp를 더해준다. (ex 4 3 2 + 4 = 4 3 24)

3. 전의수에 현재수를 그대로 붙여 현재수에 더해준다.(ex 4 3 2 + 4 = 4 3 2 4)

4. 마지막이 0으로 끝나면 안되므로 0을제외한 합을 구해준다.

n = list(map(int, input().strip()))
dp = [[0 for _ in range(35)] for _ in range(len(n))]
dp[0][n[0]] = 1

for i in range(1, len(n)):
    for j in range(1, 35):
        next = 10 * j + n[i]
        if next <= 34:
            dp[i][next] += dp[i-1][j]
        dp[i][n[i]] += dp[i-1][j]

print(sum(dp[-1][1:]))