10844 쉬운 계단 수

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

dynamic programming 문제로 풀 수 있다

예를들어 3으로 시작하는 3자리 숫자는 다음과 같다

321
323
343
345

근데 이는 자세히 보면 3으로 시작하는 3자리 숫자로 만들 수 있는 계단 수는

(2로 시작하는 2자리 숫자로 만들 수 있는 계단 수) + (4로 시작하는 2자리 숫자로 만들 수 있는 계단 수) 를 합한 것으로 표현할 수 있다

이를 일반화 하면 $j$로 시작하는 $i$자리 숫자로 만들 수 있는 계단 수는 아래와 같다

따라서 이 $j$로 시작하는 $i$자리 숫자로 만들 수 있는 계단 수를 $dp$로 메모라이즈 하면 $dp$는 아래와 같이 일반화 할 수 있다

$dp[i][j] = dp[i-1][j-1] + dp[i+1][j+1]$

다만 9로 시작하는 $i$자리 숫자에 대해서는 $9 → 10$이 불가능하기 때문에 $9 →8$에 한해서만 더하면 된다

$dp[i][j] = dp[i-1][j-1] \quad \text{,if } j+1 >= 10$

실제로 계산하면 아래와 같이 dp 이전 자리수에서 하나작은 수 + 하나 큰 수로 시작하는 dp 값을 가져와 합산하면 된다

이렇게 N번째까지 구하면 된다

따라서 N번째 행의 가짓수를 모두 더하면 되는데 유의할 점은 0으로 시작하면 안되므로 dp[0]은 제외하고 합산하면된다

$output = \sum_1^9dp[N][j]$

이를 구현한 파이썬코드는 아래와 같다

import sys

N = int(input())
dp = [[1 for i in range(10)] for j in range(N+1)]

for i in range(2, N+1):
    for j in range(10):
        if j  == 0:
            dp[i][j] = dp[i-1][j+1]
        else:
            if (j + 1) > 9:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000

r = 0
for i in range(1, 10):
    r = (r + dp[N][i]) % 1000000000

print(r)