BOJ 쉬운계단수

1. BOJ 10844 쉬운계단수

실버 1, DP

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

코드

N = int(input())
dp = []
for i in range(N):
    dp.append([0 for _ in range(10)])
dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
 
if N>=2:
    for i in range(1, N):
        for j in range(10):
            if j==0:
                dp[i][j] = dp[i-1][j+1]
            elif j==9:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
 
ans = sum(dp[N-1])
print(ans%1000000000)

설명

입력 : 자릿수, 해당 자릿수에서 계단수의 개수를 출력하는 것이 목표이다. 
계단수란, 101 210 323 처럼 각 자릿수의 차이가 1인 수이다. 0으로 시작하는 수는 없다고 한다. 

아이디어는 다음과 같다.

dp[n][i]에는 n번째 자리수에서 i로 끝나는 계단수의 개수가 기록된다. dp[n-1][i-1]+dp[n-1][i+1]로 구할 수 있었다. 물론 이때 0과 9는 예외처리가 필요하다.