DP(다이나믹 프로그래밍): 백준 15988 파이썬 1,2,3 더하기 3

문제:

https://www.acmicpc.net/problem/15988

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

 

풀이:

이 문제는 '1,2,3, 더하기 1' 9095번 문제에서 n의 범위가 크게 늘어난 문제이다.

이 문제에 9095번 문제와 같은 코드를 제출하면 메모리 초과가 발생한다. 그래서 다르게 풀어야 하는데,

먼저 다이나믹 프로그래밍 기법으로 범위 내의  방법 수를 다 구해서 리스트 'd'에 모두 저장한 뒤에 

각 테스트 케이스를 입력받아 리스트 'arr'에 그 결과를 저장한다.

입력받은 테스트 케이스를 모두 저장하고 있지 않고, 테스트 케이스에 따라 하나하나 계산하는 것이 

아니기 때문에 결과적으로 시간 복잡도와 공간 복잡도를 모두 줄일 수 있다.

 

정답:

import sys
input = sys.stdin.readline
 
n = int(input())
 
d = [0] * 1000001
 
d[1] = 1
d[2] = 2
d[3] = 4
 
for i in range(4, 1000001):
    d[i] = (d[i-1] + d[i-2] + d[i-3]) % 1000000009
 
arr = []
 
for i in range(n):
    temp = int(input())
    arr.append(d[temp])
 
for i in arr:
    print(i)