백준 15988번 1 2 3 더하기 3

전에 풀었던 1 2 3 더하기 1이랑 완전히 똑같은거 같아서 확인해보니 n의 범위가 달라졌다.

 

다만 내가 1을 풀었을 당시도 dp로 풀었기 때문에 동일하게 풀어도 상관없을듯 하다.

dp로 풀 경우 어차피 시간복잡도는 O(n)이기때문에 10^6정도는 크게 문제가 되지 않는다.

 

 

import sys

t=int(sys.stdin.readline().rstrip())

max_num=1000000

v=[0]*(max_num+1)
v[1]=1
v[2]=2
v[3]=4

for i in range(4,max_num+1):
    for j in range(1,3+1):
        v[i]+=v[i-j]
    v[i]%=1000000009

for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    print(v[n])

이렇게 작성했다.

이렇게 한번 입력에 여러번 들어오는 경우는 입력받고 나서 연산하게 하면 높은확률로 시간초과가 났었기에 미리 10^6까지 연산을 한 뒤 출력만 하게 작성했다.