백준_15988_1, 2, 3 더하기 3

'1, 2, 3 더하기' 문제는 다이나믹 프로그래밍(dp)으로 푸는 문제다. 9095번(1 ,2, 3더하기)은 재귀와 메모이제이션으로 풀었었는데, 이번에는 반복문으로 풀어보았다.

#include <iostream>
#define MAX 1000001
using namespace std;

int T, x;
long long d[MAX];

void dp(int n) {
	d[1] = 1;
	d[2] = 2;
	d[3] = 4;
	for (int i = 4; i <= n; i++) {
		d[i] = (d[i - 1] + d[i - 2] + d[i - 3]) % 1000000009;
	}
	cout << d[n] << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> x;
		dp(x);
	}
	return 0;
}