다이나믹 프로그래밍 - 백준 10844 [Python]

Problem)

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

10844번: 쉬운 계단 수

 

Solution)

연속하는 수의 차이, 마지막에 오는 수의 차이를 기록하면 된다.

따라서 1차원으로 바로 정의하기 보다는

D[i][j] = 길이가 i인 계단 수, 마지막 자리가 j인 개수로 정의하여 해결한다.

 

그리고 맨 마지막에 올 수 있는 수는 j-1이거나, j+1인 경우이기 때문에 각각 나눠서 풀도록 한다.

 

Answer)

mod = 1000000000
n = int(input())
d = [[0]*10 for _ in range(101)]
for i in range(1, 10):
    d[1][i] = 1

for i in range(1,n+1):
    for j in range(10):
        if j-1 >= 0 :
            d[i][j] += d[i-1][j-1]
        if j+1 <=9:
            d[i][j] += d[i-1][j+1]
        d[i][j]%=mod
print(sum(d[n])%mod)