백준
백준 소스코드 [C++] 15993 1, 2, 3 더하기 8
Hani_Levenshtein
2020. 10. 28. 08:34
15993번: 1, 2, 3 더하기 8
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
www.acmicpc.net
백준 소스코드 [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;
}