[백준][Python] 15988번 1, 2, 3 더하기 3

15988번: 1, 2, 3 더하기 3

 

코드

import sys
t = int(input())
dp = [0,1,2,4]

for _ in range(t):
	n = int(sys.stdin.readline())

	for i in range(len(dp),n+1):
		dp.append((dp[i-3]+dp[i-2]+dp[i-1])%1000000009)
		
	print(dp[n])

 

설명

처음에는 for문 안에 dp를 선언해서 새로운 n 값을 받을 때마다 dp 계산을 했더니 시간초과가 떴다.

 

그래서 dp를 만들어놓고 계속해서 그 값을 가져다 쓰는 방식으로 다시 코드를 짰다. 

 

예를 들어 n = 4일 때 계산을 하고 나면 dp에는 [0,1,2,4,7]이 들어있게 되고

n = 7 입력을 받았을 때는 dp[5] 부터 계산을 하면 된다.