[백준 15988] 1, 2, 3 더하기 3 [C]

백준 - 15998

---

풀이

"백준 9095, 1, 2, 3 더하기"의 확장 문제이다.

1e6 까지 미리 구해놓자.

---

소스코드

#include <stdio.h>
const int MOD = 1e9+9;
int dp[1000001] = {1, 2, 4};
int main(){   
    for (int i = 3; i < 1000001; i++)
        dp[i] = ((dp[i-1]+dp[i-2])%MOD +dp[i-3]) %MOD;
        
    int N, T;
    for (scanf("%d", &T); T--;){
        scanf("%d", &N);
        printf("%d\n", dp[N-1]);
    }
}

---

출처 및 참고자료

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

[백준 9095] 1, 2, 3 더하기 [C]