[백준] 10844 쉬운계단수 python

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

n = int(input())
dp = [[0] * 10 for _ in range(101)]
for i in range(1, 10):
    dp[1][i] = 1
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]) % 1000000000)

dp[5]까지는 직접 만들어봤는데 점화식을 잘못 세웠다

 

---

pacific-ocean.tistory.com/151

[백준] 10844번(python 파이썬)

이코드를 보면서 이해했는데 내가 생각했던걸 딱 만들어준 코드이다.

 

---

dp를 하려면 점화식을 잘 세워야하는걸 오늘 다시 깨닫는다.

아마 이번주는 머리가 말랑말랑해지게끔 조금 쉬운거 위주로 풀고

이전에 배웠던 알고리즘을 차근차근 복습해가야겠다.