10844번 파이썬

처음엔 n-1자릿수의 계단 수에 +-1을 더해서 n자리수의 계단 수를 구하는 방식으로 풀었는데

이 방식은 시간 초과뿐만 아니라 메모리도 초과됨...

import sys
input = sys.stdin.readline

n = int(input())
'''
dx = [-1,1]
stairs=[1,2,3,4,5,6,7,8,9]
if n >= 2:
    for i in range(2,101):
        if n-i < 0:
            break
        #[i-2] 에 접근
        ary=[]
        for item in stairs:
            for k in range(2):
                #끝자리만 확인
                s_item=str(item)
                x = int(s_item[len(s_item)-1])+dx[k]
                if 0<=x<=9:
                    txt=s_item+str(x)
                    ary.append(int(txt))
        stairs=ary
print(len(stairs))
'''

다른 사람의 방식을 봤더니 대부분 규칙을 이용한 dynamic programming 기법을 이용하는것 같음

끝자리가 0인 경우는 1의 의해서만 영향을 받기 때문에 j=0일 때는 새로운 dp값은 dp[i-1][1]이 되고

끝자리가 9인 경우는 8의 의해서만 영향을 받기 때문에 j=9일 때 마찬가지로 dp[i-1][8]이 된다.

나머지의 경우인 1 ~ 8은 그 전 순서의 자릿 수에 +-1에 영햐ㅐㅇ을 받으므로 dp[i-1][j-1]+dp[i-1][j+1]이 된다.

import sys
input = sys.stdin.readline

n = int(input())

dp = [[0]*10 for _ in range(n+1)]

#n의 길이가 1일 경우 전부다 하나
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)