[백준] 10844. 쉬운 계단 수(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 10844. 쉬운 계단 수

시간 제한	메모리 제한	난이도
1초	256 MB	실버 1

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

✔️ 입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

✔️ 출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

✔️ 입력 출력 예시

입력	출력
1	9
2	17

🗒️ 내 풀이

[백준] 15990. 1, 2, 3 더하기 5 와 거의 비슷한 유형의 문제여서 쉽게 해결할 수 있었다. 마찬가지로 1,000,000,000으로 나눈 나머지를 출력한다 라는 문구에서 다이나믹 프로그래밍으로 접근할 수 있었다.

계속해서 뒷자리에 숫자를 추가한다고 가정 했을 때, 0과 9를 추가하는 경우를 제외하면 모두 +1, -1 숫자 2가지를 추가할 수 있다. 즉, dp[n][i] 는 n자리 수의 마지막 숫자가 i인 경우의 수라고 하면 점화식은 다음과 같다.

• 0일 경우 : dp[n][0] = dp[n - 1][1]
• 9일 경우 : dp[n][9] = dp[n - 1][9]
• 나머지    : dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k + 1]

import sys
input = sys.stdin.readline
MOD = 1000000000

n = int(input())
dp = [[0] * 10 for _ in range(n + 1)]

for i in range(1, 10):
    dp[1][i] = 1

# dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k + 1] (1 <= k <= 8)
# dp[n][0] = dp[n - 1][1]
# dp[n][9] = dp[n - 1][8]
for i in range(2, n + 1):
    dp[i][0] = dp[i - 1][1] % MOD
    dp[i][9] = dp[i - 1][8] % MOD
    for k in range(1, 9):
        dp[i][k] = (dp[i - 1][k - 1] + dp[i - 1][k + 1]) % MOD

print(sum(dp[n]) % MOD)