백준 10844 쉬운 계단 수

과정

• https://ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-10844%EB%B2%88-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98-CDP 이 블로그 글을 참고하였다.
• 2차원 DP 문제.
• 행 인덱스를 수 길이, 열 인덱스를 끝나는 숫자라고 생각한다.
• i 길이의 수 중, j 로 끝나는 수의 개수는 i-1 길이의 수 중, j-1로 끝나는 수의 개수와 j+1로 끝나는 수의 개수 합과 같다.
• 0, 9의 경우는 이어질 수 있는 수가 각각 1, 8로 한 가지밖에 없다는 점에 주의한다.

N = int(input())
dp = [[0] * 10 for _ in range(N + 1)]
# 길이를 행 인덱스로, 끝나는 수를 열 인덱스로 생각함.
for i in range(1, N + 1):
    if i == 1:
        dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    else:
        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]
print(sum(dp[N]) % 1000000000)