백준 소스코드 [C++] 15993 1, 2, 3 더하기 8

www.acmicpc.net/problem/15993

15993번: 1, 2, 3 더하기 8

백준 소스코드 [C++] 15993 1, 2, 3 더하기 8

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
ll odd[100001];
ll even[100001];
void solve(int n) {
	for (int i = 4;i <= n;i++) {
		if (even[i] == 0)even[i] = (odd[i - 1] + odd[i - 2] + odd[i - 3]) % 1000000009;
		if (odd[i] == 0)odd[i] = (even[i - 1] + even[i - 2] + even[i - 3]) % 1000000009;

	}
	cout << odd[n] <<" "<<even[n]<< '\n';
	return;

}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int t, n;
	cin >> t;
	odd[1] = 1;
	odd[2] = 1;
	odd[3] = 2;
	even[1] = 0;
	even[2] = 1;
	even[3] = 2;
	while (t--) {
		cin >> n;
		solve(n);
	}
	
	return 0;
}