백준 10844 - 쉬운 계단 수 (파이썬)

분류 : 다이나믹 프로그래밍

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

풀이

먼저 문제 이해를 하면 다음과 같다.

1. 계단 수는 인접한 모든 자리의 차이가 1인 수이다.
2. N이 주어질 때, 깊이가 N인 계단 수의 갯수를 구하는 문제이다.
3. 0으로 시작하는 수는 계단 수가 아니다.
4. 결과는 10^9로 나눈 나머지를 출력해야한다.

문제 풀이를 위해서 DP 알고리즘을 사용한다.

1. dp[i][j]를 길이가 j이고 마지막 숫자가 i인 계단 수의 갯수라고 정의한다.
2. 점화식을 세우면 다음과 같다.
   • dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]
   • 즉, 길이가 i이고 끝자리가 j인 계단 수는 이전 자리(i-1)에서 끝자리가 j-1이거나 j+1이었던 경우의 합이다.
3. 초기 조건으로는
   • dp[0][1] = 0 (0으로 시작하는 계단 수는 불가능)
   • dp[i][1] = 1 (1~9까지의 숫자는 각각 한 자리 계단 수)

시간 복잡도 분석

• N의 최대값은 100
• dp 배열의 크기는 10 x N
• 이중 for 루프 (10 * N번 연산)
• 시간 복잡도: O(N)
• O(N)O(N)

코드

# 백준 10844 - 쉬운 계단 수
# 분류 : 다이나믹 프로그래밍

import sys
input = sys.stdin.readline

N = int(input())
mod = 1000000000

dp = [[0] * (N + 1) for _ in range(10)] # 10 x (n + 1) 배열

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

for i in range(2, N + 1) :
    for j in range(10) :
        dp[j][i] = 0

        if j > 0 :
            dp[j][i] += dp[j - 1][i - 1]
            dp[j][i] %= mod
        if j < 9 :
            dp[j][i] += dp[j + 1][i - 1]
            dp[j][i] %= mod

answer = 0
for i in range(10) :
    answer += dp[i][N]
    answer %= mod

print(answer)