[백준] 10844. 쉬운 계단 수

첫 풀이(시간초과....)

def stair(num):
    num=list(map(int,str(num)))
    for i in range(1,len(num)):
        k=abs(num[i]-num[i-1])
        if k!=1:
            return False
    return True
count=0
for i in range(10**(n-1),10**n):
    if stair(i)==True:
        count+=1
print(count)

정답(인터넷 참고함...)

import sys
n=int(sys.stdin.readline())
dp=[[0]*10 for _ in range(n+1)]
for i in range(1,10):#n이 1일때 (한자리 수일때)
    dp[1][i]=1 #1~9 모두 계단수
for i in range(2,n+1): #n이 2이상일때 (두자리 수 이상일때)
    for j in range(10):
        if j==0: # 0
            dp[i][j]=dp[i-1][1]
        elif j==9: #2일때 98, 3일때 989, 4일때 9898 ...
            dp[i][j]=dp[i-1][8] # 1개
        else:
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])
print(sum(dp[n])%1000000000)