[BOJ]백준 15988번: 1, 2, 3 더하기 3(C++)/DP

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

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

오랜만에 DP 기본문제

숫자가 커질 수 있으니 계산 과정에서 나머지 연산을 꼭 해줘야 한다 !!

처음에 최대 숫자까지 미리 계산해준 뒤 입력에 따라 출력만 제대로 해주면 끝

#include <cstdio>
#define MOD 1000000009

int n, tc, dp[1000005] = { 0,1,2,4 };

int main() {
	for (int i = 4; i <= 1000000; i++) {
		dp[i] = (dp[i - 3] + dp[i - 2]) % MOD;
		dp[i] = (dp[i - 1] + dp[i]) % MOD;
	}
	scanf("%d", &tc);
	for (int t = 0; t < tc; t++) {
		scanf("%d", &n);
		printf("%d\n", dp[n]);
	}
	return 0;
}