[백준 10844] 쉬운 계단 수

Top-Down 방식으로 작성한 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
dp = [[0]*10 for _ in range(N+1)]
def f(n,k):
    if n == 0:
        return dp[n][k]
    if n == 1:
        if k == 0:
            dp[n][k] = 0
        else: dp[n][k] = 1
    elif k == 0 :
        dp[n][k] = f(n-1, k+1)
    elif k == 9:
        dp[n][k] = f(n-1, k-1)
    else:
        dp[n][k] = f(n-1, k-1) + f(n-1, k+1)
    return dp[n][k]
num = 1_000_000_000
s = f(N,0) + f(N,1) + f(N,2) + f(N,3) + f(N,4) + f(N,5) + f(N,6) + f(N,7)+ f(N,8)+ f(N,9)
print(s % num)

시간초과아아아당

Bottom-up 방식으로 재구현

import sys
input = sys.stdin.readline
N = int(input())
dp = [[0]*10 for _ in range(N+1)]
for i in range(N+1):
    for j in range(10):
        if i == 0:
            dp[i][j] = 0
        if i == 1:
            if j == 0:
                dp[i][j] = 0
            else: dp[i][j] = 1
        elif j == 0:
            dp[i][j] = dp[i-1][j+1]
        elif j == 9:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
num = 1_000_000_000
print((dp[N][0] + dp[N][1]+dp[N][2]+dp[N][3]+dp[N][4]+dp[N][5]+dp[N][6]+dp[N][7]+dp[N][8]+dp[N][9]) % num)

개인적으로 재귀 함수가 익숙하지 않아서 그런지, Bottom-up 방식을 사용하는 편이 좋은 것 같다.

---

배운 점

1. DP는 점화식만 잘 찾으면 구현하는 데 어렵지 않다.
   하지만 점화식 찾는 게 어려움... 나의 문제 해결력 한계를 시험해보는 것 같음