15990번: 1, 2, 3 더하기 5

문제접근🤔

놓쳤던 부분😅

코드😁

5024 KB

4 ms

#include <iostream>
using namespace std;

#define MAX 1000000009

int main(void) {
	int t;
	int input;
	long long dp[100001][4];

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> t;

	dp[1][1] = 1;
	dp[2][2] = 1;
	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;

	for (int i = 4; i <= 100000; i++) {
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MAX;
		dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MAX;
		dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MAX;
	}

	for (int i = 0; i < t; i++) {
		cin >> input;
		cout << (dp[input][1] + dp[input][2] + dp[input][3]) % MAX << "\\n";
	}
	return (0);
}