[백준][python]10844.쉬운계단수 - DP

• 백준 10844 쉬운 계단 수 Silver I
• 문제링크

10844번: 쉬운 계단 수

나의 접근

DFS 로직으로 가장 뒷자리의 숫자에 +1, -1 한 경우에 대해 깊이우선 탐색을 진행해주고 N의 길이까지 탐색을 완료하면 count를 더 해주는 식으로 구현해봤는데.. 시간초과가 났다. 아래는 해당 코드다. 

import sys

def dfs(startnum, idx):
    global count
    change = [1, -1]
    if idx == N - 1:
        count += 1
        return count

    for calc in range(2):
        newnum = startnum + change[calc] #2
        if 0 <= newnum <= 9:
            if not visited[idx + 1][newnum]:
                visited[idx + 1][newnum] = 1
                dfs(newnum, idx + 1)
                visited[idx + 1][newnum] = 0

N = int(sys.stdin.readline())

if N == 1:
    print(9)

else:
    arr = [0 for _ in range(N)]
    count = 0
    for i in range(1, 10):
        # for tracking visited numbers
        visited = [[0] * 10 for _ in range(N)]
        dfs(i, 0)
    
    print(count % 1000000000)

역시나 나는 DP적 사고까진 아직 먼 것 같다..

다른 분의 접근을 참고해서 구현해본 코드다. 일의 자리에 0~9까지의 경우의 수를 1로 다 초기화시킨 다음에 자릿수를 하나씩 늘려가면서 이전 자릿수에서 경우의수를 받아오는 것이 로직의 관건이다. 

import sys
N = int(sys.stdin.readline())
dp = [[0 for i in range(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)