[백준] 10844번: 쉬운 계단 수

문제

백준 - 10844번: 쉬운 계단 수

분석

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 문제이다.
계단 수는 인접한 모든 자리의 차이가 1인 수를 말한다.

i는 i자리 까지 고려했을 때를 의미하고, j는 끝자리가 j인 상황을 의미한다.
dp[i][j]는 한 자리 적은 숫자의 상황(dp[i-1])에서 1 뺀 값과 1을 더한 값으로 부터 경우의 수를 더하게 된다. 그런데 j-1이 0보다 작아지거나 j+1이 9보다 커지는 상황은 예외처리한다.
그리고 숫자가 매우 커지는 상황을 방지하기 위해 10^9(MOD)으로 나눈 나머지를 계산해준다.
마지막 dp[n]을 모두 더하고 이 역시 MOD로 나눈 나머지를 출력한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

MOD = 10**9
n = int(input())
dp = [[0]*10 for _ in range(n+1)]
dp[1] = [0]+[1]*9
for i in range(2, n+1):
    for j in range(10):
        if j-1 >= 0:
            dp[i][j] += dp[i-1][j-1]%MOD
        if j+1 < 10:
            dp[i][j] += dp[i-1][j+1]%MOD

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

끝으로..

다이나믹 프로그래밍의 기초 문제를 풀어봤다.
DP문제 기초를 계속 다져봐야겠다.