[알고리즘] 10844번 계단수

---

코드 (시간 오류)

import sys

N = int(sys.stdin.readline())
num = []
sub_num = []
res = 0

for i in range(1,10):
    num.append([i])

for k in range(1,N):        #반복 횟수
    for i in range(9):   #root 노드 개수
        for j in range(len(num[i])):    #leaf 노드 개수
            if num[i][j] == 0:
                sub_num.append(1)
            elif num[i][j] == 9:
                sub_num.append(8)
            else:
                sub_num.append(num[i][j]-1)
                sub_num.append(num[i][j]+1)
        num[i] = sub_num.copy()
        sub_num.clear()

for i in range(9):
    res += len(num[i])

print(res)

본인이 짠 코드는 위와 같다. 우선 1부터 9까지의 숫자를 배열에 넣은 다음 반복문으로 각 숫자의 +1 -1 숫자를 임시 배열에 넣은 후 임시 배열의 값들을 기존 배열에 카피한다.
결과로 시간 초과가 났는데, 이제 와서 보니 시간 초과가 날 만 한 코드인 것 같다. 너무 반복을 많이 하게 된다.
그래서 효율적인 방법을 찾아야지 하고 보니 k변수를 이용한 반복문을 일단 없애야할 것 같다는 생각을 하게 되었다.
수를 늘려서 같은 행동을 반복하게 하는 것보단 수량화해서 패턴을 찾는 것이 효율적일 것이다.

코드

import sys

N = int(sys.stdin.readline())
num = [[0 for i in range(10)] for j in range(N+1)]
res = 0

for i in range(1,10):       #1자리수의 계단수
    num[1][i] = 1

for i in range(2,N+1):   
    for j in range(10):    
        if j == 0:
            num[i][j] = num[i-1][1]
        elif j == 9:
            num[i][j] = num[i-1][8]
        else:
            num[i][j] = num[i-1][j-1] + num[i-1][j+1]

print(sum(num[N]) % 1000000000)

이전 자리 숫자에서 계단수를 저장한 후 한 숫자에서 0과 9로 가는 경우를 제외하고 계단수가 되는 수를 계속 더해나간다.
마지막 N자리수에 있는 계단수의 개수들을 전부 합하면 결과값이 나오게 된다.