[백준/C++] 15993 1,2,3 더하기 8

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

해당 문제는 더하기 7을 풀고나면 쉽게 풀립니다. 이런 문제는 무엇을 요구하냐면?

정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는데, n을 나타낼 때 사용한 수의 개수가 홀수인 방법의 수와 짝수인 방법의 수를 공백으로 구분해 출력하라는 말입니다.

이러 문제는 이전에도 풀었는데, 잘 생각해봐야합니다. 우리는 홀수와 짝수를 구하는 문제인데 어떻게 하면 홀수와 짝수를 잘 구해낼 수 있을까? 이런 문제는 쪼개보는겁니다.

하지만 이 문제를 풀기 전에 그냥 10만이라는 숫자를 보지 못해서 이전에 풀었던거 날먹으로 해결하려고 했으나, 10만에 10만이라 저어어어얼대 시간내로 해결할 수 없어서 새로운 점화식을 생각해야했다.

날먹이 나쁜건 아닌데...

어쨌든, 그렇다면 홀수와 짝수를 다 계산할 수가 없으니 우리는 숫자 1이 홀수, 짝수를 어떻게 갖고 있는지 2가 홀수, 짝수를 어떻게 갖고 있는지? 이것을 확인하면 되지 않을까? 라는 생각을 해서 천천히 문제를 해결하려고 시도했는데...

역시나 쉽게 나와 주셨다.

n = 1 일때 홀수 1개 짝수 0개

n = 2 일때 홀수 1개 짝수 1개

n = 3 일때 홀수 2개 짝수 2개...

n = 4 일때? 어떻게 되냐면? dp[4] = dp[n - 3] + dp[n - 2] + dp[n - 1] 이 가능하다를 알 수 있다. 

어떻게? 홀수 짝수를 나눠서 계산해주면 된다. 이런 문제가 요즘은 재밌는것 같다. 생각하는데 시간이 오래걸리지만 그래도 생각을 다양하게 시도할 수 있어서 머리가 좀 깨지는 것을 감수하고 도전해야할 것 같다.

#include<iostream>

#define MAX 100010
using namespace std;

int testCase;
long long odd[100001],even[100001];

int main() {
	
	odd[1] = 1, odd[2] = 1, odd[3] = 2;
	even[1] = 0, even[2] = 1, even[3] = 2;
	
	for(int i = 4; i <= 100000; i++){
		odd[i] = (even[i - 1] + even[i - 2] + even[i - 3]) % 1000000009;
		even[i] = (odd[i - 1] + odd[i - 2] + odd[i - 3]) % 1000000009;
	}
	
	cin >> testCase;
	
	while(testCase--){
		
		int n; cin >> n;
		
		cout << odd[n] << " " << even[n] << "\n";
		
	}
	
	
	return 0;
}