[백준] 10844 '쉬운 계단 수' 파이썬(python)

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

10844번: 쉬운 계단 수

N = int(input())

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

MOD = 1000000000

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

Point

• 규칙을 찾아 DP를 활용한 문제
• dp테이블은 이차원리스트
• 규칙을 들여다보면 N = 3 부터 앞의 결과들을 그대로 이용한다는 것을 알 수 있음
• j == 0 이거나 j == 9인 예외 사항들을 잘 체크하고 식을 적용하면 되는 문제