백준 알고리즘 10844번: 쉬운 계단 수 python

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

문제 접근

• 계단 수란 각 자리수마다 인접한 숫자의 차이가 1인 수를 의미한다.
  예) 45656 → 계단 수 (4→5→6→5→6 차이가 모두 ±1)

• 길이가 N인 계단 수의 개수를 구하라는 문제이다. 단, 0으로 시작하는 수는 계단 수가 아니다.

• 점화식(DP)으로 해결 가능하다.

풀이 아이디어

• dp[i][j] = i자리 수에서 마지막 자릿수가 j일 때의 계단 수 개수

• 초기값: dp[1][1~9] = 1 (0으로 시작하는 수는 제외)

• 점화식:

  • dp[i][0] = dp[i-1][1]
  • dp[i][9] = dp[i-1][8]
  • dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] (1 ≤ j ≤ 8)

• 최종 정답은 dp[N][0] + dp[N][1] + ... + dp[N][9]의 합

해답 및 풀이

import sys
input = sys.stdin.readline

MOD = 1000000000

N = int(input())

# dp[i][j] = 길이가 i이고, 마지막 숫자가 j인 계단 수의 개수
dp = [[0] * 10 for _ in range(N + 1)]

# 초기값: 길이가 1일 때 1~9는 모두 1개씩 존재 (0으로 시작하는 수는 제외)
for i in range(1, 10):
    dp[1][i] = 1

# 점화식 계산
for i in range(2, N + 1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i - 1][1]  # 0은 이전 자리수가 1일 때만 가능
        elif j == 9:
            dp[i][j] = dp[i - 1][8]  # 9는 이전 자리수가 8일 때만 가능
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

        dp[i][j] %= MOD  # 문제에서 1,000,000,000으로 나눈 나머지 요구

# 정답: 길이가 N인 계단 수의 총 개수
print(sum(dp[N]) % MOD)