백준 15989 1,2,3 더하기 4

dp + 2차원 리스트

t = int(input())

for _ in range(t):
    n = int(input())
    
    d = [[0] * (3) for _ in range(n + 1)] 
    d[0] = [0, 0, 1]
    d[1] = [1, 0, 0]
    
    for i in range(2, n+1):
        if i - 1 < 0:
            continue
        d[i][0] = sum(d[i-1])
        if i - 2 < 0:
            continue
        d[i][1] = sum(d[i-2][1:3])
        if i - 3 < 0:
            continue
        d[i][2] = d[i-3][2]
        
    print(sum(d[n]))

1차시도 : 시간 초과를 생각을 안함

t = int(input())

def ops(n, u, d):
    for i in range(2, n+1):
        if i - 1 < 0:
            continue
        d[i][0] = sum(d[i-1])
        if i - 2 < 0:
            continue
        d[i][1] = sum(d[i-2][1:3])
        if i - 3 < 0:
            continue
        d[i][2] = d[i-3][2]
    return d
    
u = 0
d = [[0] * (3) for _ in range(10000 + 1)] 
d[0] = [0, 0, 1]
d[1] = [1, 0, 0]

for _ in range(t):
    n = int(input())
    if n == 1 or n == 0:
        print(sum(d[n]))
    if n > u:
        d = ops(n, u, d)
        print(sum(d[n]))
    else:
        print(sum(d[n]))
    u = n

2차시도 : ...

t = int(input())

d = [[0] * (3) for _ in range(10000 + 1)] 

d[0] = [0, 0, 1]
d[1] = [1, 0, 0]

for i in range(2, 10000+1):
    if i - 1 < 0:
        continue
    d[i][0] = sum(d[i-1])
    if i - 2 < 0:
        continue
    d[i][1] = sum(d[i-2][1:3])
    if i - 3 < 0:
        continue
    d[i][2] = d[i-3][2]

for _ in range(t):
    n = int(input())
    print(sum(d[n]))

정답 : n의 범위가 10000밖에 안되는데 한번에 계산하는게 빠르다
복습 + 시간복잡도 계산