[백준] 15993. 1, 2, 3 더하기 8(c++)

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

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

 

누가봐도 dp 문제였다.

다만 규칙 찾기가 쉽지 않았는데 문제에 힌트가 숨어있었다.

홀수와 짝수를 구분해서 출력하라고 했는데, 다음과 같은 규칙이 있었다. 

 

i>3일 때, 홀수[i] = 짝수[i-1] + 짝수 [i-2] + 짝수[i-3], 짝수[i] = 홀수[i-1] + 홀수 [i-2] + 홀수[i-3]인 규칙이다.

이것만 해결하면 끝이다.

---

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <cstring>
using namespace std;

using ll = long long;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll t, Max = 0;

	cin >> t;

	vector<ll> save(t);

	for (ll i = 0; i < t; i++) {
		cin >> save[i];
		Max = max(save[i], Max); // DP 할 범위 설정
	}
	vector<ll> a(Max+1), b(Max+1); 

	if (Max > 3) {
		a[1] = 1;
		b[1] = 0;
		a[2] = 1;
		b[2] = 1;
		a[3] = 2;
		b[3] = 2;
	}
	else { // 3 이하 일 때 수동 출력
		for (ll i = 0; i < t; i++) {
			if (save[i] == 1) {
				cout << "1 0\n";
			}
			else if (save[i] == 2) {
				cout << "1 1\n";
			}
			else if (save[i] == 3) {
				cout << "2 2\n";
			}
		}
		return 0;
	}

	for (ll i = 4; i <= Max; i++) {
		a[i] = (b[i - 1] + b[i - 2] + b[i - 3]) % 1000000009;
		b[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 1000000009;
	}

	for (ll i = 0; i < t; i++) {
		cout << a[save[i]]  << " " << b[save[i]] << '\n';
	}

	return 0;
}