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

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

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

 

문제해결

ＤＰ를　공부했으면　굉장히　쉽게　풀었을　수　있다．

ｎ을　숫자　１，２，３의　합으로　나타내는　방법의　수를　ｄｐ［ｎ］이라고　하면，

ｄｐ［ｎ］　＝　ｄｐ［ｎ－１］　＋　ｄｐ［ｎ－２］　＋　ｄｐ［ｎ－３］

왜냐하면　ｎ－１를　　숫자　１，２，３의　합으로　나타낸　후　숫자　１을　더한　것의　개수는　ｄｐ［ｎ－１］과　동일　

ｎ－２를　숫자　１，２，３의　합으로　나타낸　후　숫자　２를　더한　것의　개수는　ｄｐ［ｎ－２］과　동일하며

ｎ－３을　숫자　１，２，３의　합으로　나타낸　후　숫자　３을　더한　것의　개수는　ｄｐ［ｎ－３］과　동일하기　때문이다．　

 

ＣＯＤＥ

import sys
input = sys.stdin.readline

t = int(input())
dp = [0 for _ in range(1000001)]
dp[1] = 1
dp[2] = 2
dp[3] = 4
dp[4] = 7 # dp[3] + dp[2] + dp[1]
for i in range(5, 1000001):
    dp[i] = dp[(i-1)]%1000000009 + dp[(i-2)]%1000000009 + dp[(i-3)]%1000000009　
    ＃　이렇게　안하면　메모리　초과가　뜬다．ㅜㅜ
for _ in range(t):
    n = int(input())
    print(dp[n]%1000000009)