[BOJ] 15988번 - 1,2,3 더하기 3

---

문제설명

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

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

사고과정

• 1,2,3 더하기 문제랑 동일한 점화식인 문제이다.
• 단, 주어지는 데이터 범위만 차이가 있다. 주어진 범위가 백만이라 입력 데이터를 받을 때 sys 라이브러리를 활용했다.
• 점화식은 다음과 같다. $dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$
• 참고로 n = 3일 때까지는 직접 경우의 수를 구해주어서 DP 테이블에 넣어주어야 한다. 그러므로 n이 1,2,3일 때는 개별로 처리하도록 해준다. 만약 안해주면 IndexError가 발생한다.

풀이

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    n = int(input())
    if n == 1 or n == 2:
        print(n)
        continue
    if n == 3:
        print(4)
        continue

    mod = int(1e9) + 9
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4

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

    print(dp[n])