[백준] 15988 1,2,3 더하기 3 파이썬 python

문제링크

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

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

코드

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

 

POINT

- DP로 접근

- n번째 할 수 있는 행동 : +1, +2, +3

d[i] : 정수 i를 1, 2, 3의 합으로 나타내는 경우의 수

d[i] = d[i-1]+d[i-2]+d[i-3] (i>3)

ex) 4를 만드는 방법 d[4] = {(총합 3인 case,d[3]) 3 + 1} +{(총합 2인 case,d[2]) 2 + 2} +{(총합 1인 case,d[1]) 1 + 3}