10844번 - 쉬운 계단 수(Python)

풀이

dp를 이용해 계단 수를 저장한다.

 

dp[i][j]는 자릿수가 i이고, 끝자리가 j인 계단 수를 의미한다.

자릿수가 1일때는 1부터 9까지만 1을 대입한다.(0이 올 수 없으므로)

이후에는 자릿수가 하나 적고, 끝자리가 j-1, j+1인 경우를 더해서 dp에 대입하면 된다.

(dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1], j가 10일 때 dp값을 모두 0으로 초기화했기에 9를 따로 신경쓰지 않는다.)

코드

N = int(input())
dp = [[0 for _ in range(11)] for _ in range(N+1)]

for a in range(1, 10):
    dp[1][a] = 1
for i in range(2, N+1):
    for j in range(10):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[N]) % 1000000000)