088 쉬운 계단 수

첫번째 코드

 

dp에서는 점화식을 세우는 방법의 아이디어를 보면서

이런게 있구나~ 라는 생각을 먼저 하는 것이 중요하다!!

 

점화식은 오로지 하나로 구성된 것이 아니고 나누어서 생각해야 한다!

코드는 책을 참고했다!

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [[0 for _ in range(11)] for i in range(n+1)]
mod = 1000000000

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

for i in range(2, n+1):
    dp[i][0] = dp[i-1][1]
    dp[i][9] = dp[i-1][8]
    for j in range(1, 9):
        dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod

answer = 0

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

print(answer)

 

통과!

점화식 세우기 연습이 필요하다!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/10844.%E2%80%85%EC%89%AC%EC%9A%B4%E2%80%85%EA%B3%84%EB%8B%A8%E2%80%85%EC%88%98

programmers/백준/Silver/10844. 쉬운 계단 수 at main · ornni/programmers