백준 10844번: 쉬운 계단 수 (Python)

접근

백준 단계별 문제 동적 계산법을 착실히 풀어왔다면 쉽게 풀 수 있다.

2021.03.28 - [SW/백준 (Python)] - 백준 1463번: 1로 만들기 (Python)

백준 1463번: 1로 만들기 (Python)

다음의 접근 방법을 이용하여 점화식을 만들면 쉽게 풀 수 있다.

길이가 N인 i로 끝나는 계단 수의 개수
= 길이가 N-1인 i-1로 끝나는 계단 수의 개수 + 길이가 N-1인 i+1로 끝나는 계단 수의 개수

코드

import sys


n = int(sys.stdin.readline())
dp = [[0 for _ in range(12)] for __ in range(n)]
dp[0] = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
for i in range(1, n):
    for j in range(1, 11):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[-1]) % 1000000000)

더 생각해 볼 것?

...