BOJ #10844 쉬운 계단 수

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #10844 쉬운 계단 수

문제 풀이

하위 문제 결과를 저장하는 배열 구성을 파악하지 못하면 해결하기 힘든 문제다. 보통 DP 배열을 1차원으로 작성하지만 이 문제는 길이 N의 계단 수를 생성할 때 길이 N - 1의 계단 수와 그 계단 수의 마지막 자리 수에 의존한다. 따라서, [길이][끝자리 수]라는 2차원 배열로 관리하며 길이 N인 계단 수는 sum(dp[N])이 될 것이다.

• dp 배열 초기화 (row = N + 1, col = 10)
• 초기 값은 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• 길이 2부터 만약 일의 자리 수가 0이나 9면 길이 i - 1 계단 수의 일의 자리 수가 1이거나 8이어야 한다. 나머지는 일의 자리수 k에 대해 dp[i - 1][k - 1] + dp[i - 1][k + 1]이 성립한다.
• 마지막까지 진행한 후 sum(dp[N]) 출력

python 코드

import sys

input = sys.stdin.readline

N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N + 1)]
for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, N + 1):
    dp[i][0] = dp[i - 1][1]
    dp[i][9] = dp[i - 1][8]
    for j in range(1, 9):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[N]) % 1000000000)