BOJ 15993 - 1, 2, 3 더하기 8

1, 2, 3 더하기 8 - - 🥈 Silver 1

• 문제 링크
  https://www.acmicpc.net/problem/15993

dynamic programing 문제다. 규칙성을 찾고 규칙에 맞는 점화식을 찾고자 가장 첫 케이스인 1부터 적어보았다.

1
1
✍️ 홀수 : 1 / 짝수 : 0

2
1 1
2
✍️ 홀수 : 1 / 짝수 : 1

3
1 1 1
2 1
1 2
3
✍️ 홀수 : 2 / 짝수 : 2

4
1 1 1 1
2 1 1
1 2 1
1 1 2
2 2
3 1
1 3
✍️ 홀수 : 3 / 짝수 : 4

5
1 1 1 1 1
2 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
2 2 1
2 1 2
1 2 2
3 1 1
1 3 1
1 1 3
3 2
2 3
✍️ 홀수 : 7 / 짝수 : 6

각 경우를 나열해보면 아래와 같다.

1부터 5까지 정리
✍️ 홀수 : 1 / 짝수 : 0
✍️ 홀수 : 1 / 짝수 : 1
✍️ 홀수 : 2 / 짝수 : 2
✍️ 홀수 : 3 / 짝수 : 4
✍️ 홀수 : 7 / 짝수 : 6

4번째부터 자세히 살펴보면 홀수는 바로 이전 짝수 3개의 합 3 = 2 + 1 + 0 이며, 짝수 역시 이전 홀수 3개의 합 4 = 2 + 1 + 1 임을 알 수 있다.

이러한 규칙성으로 작성한 코드는 아래와 같다.

풀이 코드

#include <iostream>
#include <vector>
#define MOD 1000000009
using namespace std;

long long T, N;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<pair<long long, long long>> result;
	result.push_back({ 1, 0 });
	result.push_back({ 1, 1 });
	result.push_back({ 2, 2 });

	for (int i = 3; i < 100000; i++) {
		result.push_back({ 
			(result[i - 1].second + result[i - 2].second + result[i - 3].second) % MOD ,
			(result[i - 1].first + result[i - 2].first + result[i - 3].first) % MOD 
			});
	}

	cin >> T;

	while (T--) {
		cin >> N;
		cout << result[N - 1].first << " " << result[N - 1].second << "\n";
	}

	return 0;
}

결과