[baekjoon] 백준 15988번(파이썬): 1, 2, 3 더하기 3

문제

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

알고리즘

- dp를 통해 문제를 수행한다.

- 규칙을 찾아보면 4부터 dp[n] = dp[n-3]+dp[n-2]+dp[n-1] 이라는 점화식을 구할 수 있다.

- 1000001가지의 dp 값을 구하고 문제에 원하는 위치에 값을 출력한다.

코드

import sys


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

dp = [0] * 1000001

dp[1] = 1
dp[2] = 2
dp[3] = 4

for i in range(4, 1000001):
    dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009

[print(dp[j]) for j in n]

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법