[백준/Python3] 1, 2, 3 더하기 3

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

풀이

Dynamic Programming의 대표적인 문제 중 하나인 1, 2, 3더하기 문제다. dp[3]까지 초기화 해둔 뒤, 아래의 공식을 이용해 해결할 수 있다.

dp[i] = dp[i-3] + dp[i-2] + dp[i-1]

mod 연산을 제대로 취하지 않으면 Memory Error가 발생하므로 dp[i]를 구할 때 마다 해야한다.

코드

# Initial
answer = list()
mod = 1000000009
MAX = 1000000

# Make DP table
dp = [0 for _ in range(MAX + 1)]
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, MAX + 1):
    dp[i] = (dp[i-3] + dp[i-2] + dp[i-1]) % mod

# Answer
for _ in range(int(input())):
    n = int(input())
    answer.append(dp[n])

print('\n'.join(map(str, answer)))