[못 푼 문제] 백준 10844번

n = int(input())
dp = [[0 for i in range(10)] for j 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)

위와 같이 풀면 시간 복잡도가 켜져서 망한다.

n = int(input())
d = [1] * 10
d[0] = 0
for i in range(2, n+1):
    temp = [0] * 10
    for j in range(10):
        if 0 < j < 9:
            temp[j] = d[j-1] + d[j+1]
        elif j == 0:
            temp[j] = d[1]
        else:
            temp[j] = d[8]
    d = temp
    print(d)
s = 0
for i in range(10):
    s += d[i]
print(s % 1000000000)

2차원 배열을 했으면 더 빨리 풀었을텐데