[BOJ] 18249 - 욱제가 풀어야 하는 문제

1. 문제 해석

• 각각의 빨간색 정점과 파란색 정점이 N개가 있다. 각 정점은 1~N의 번호를 가진다.
• 1 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다.
• 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i-1번 정점과 파란색 i번 정점을 연결하는 간선이 존재한다.
• 2 ≤ i ≤ N인 자연수 i에 대해 빨간색 i번 정점과 파란색 i-1번 정점을 연결하는 간선이 존재한다.
• 서로 다른 간선의 끝점을 공유하지 않도록 N개의 간선을 선택하는 방법의 수를 구해야 한다.
  (1 <= N <= 191,229, 정답을 10e9+7로 나눈 나머지를 출력)

 

2. 접근방법

• <그림1>과 <그림2>에서 알 수 있듯이 4번 정점의 간선 선택은 이전 정점까지의 선택과 연관되어 있다.
• <그림1>과 같이 빨간색 정점 4번과 파란색 정점 4번을 연결하는 간선을 선택할 경우 정점 3번까지 3개의 간선을 선택하는 방법의 수와 같다.
• <그림2>와 같이 빨간색 정점 3번과 파란색 정점 4번, 빨간색 정점 4번과 파란색 정점 3번을 연결하는 간선을 선택할 경우 정점 2번까지 2개의 간선을 선택하는 방법의 수와 같다.
• 결국 [정점 4번까지 4개의 간선]을 선택하는 방법은 [정점 3번까지 3개의 간선]을 선택하는 방법의 수와 [정점 2번까지 2개의 간선]을 선택하는 방법의 수를 합하면 된다.
• 따라서 d[N]을 정점 N번까지 N개의 간선을 선택하는 방법이라고 하면 d[N] = d[N - 1] + d[N - 2]가 된다

 

3. 주의할 점

• [N = 2]인 경우 N개의 간선을 선택하는 2가지 방법이 있다.

4. 소스코드

	#include <iostream>
	#include <algorithm>
	#define MAX 191230

	using namespace std;

	int T, N;
	int d[MAX];
	int mod = 1000000007;

	int main() {
		ios::sync_with_stdio(false);
		cin.tie(0);

		d[1] = 1, d[2] = 2;
		for (int i = 3; i < MAX; i++) {
			d[i] = (d[i - 2] + d[i - 1]) % mod;
		}

		cin >> T;
		while (T--) {
			cin >> N;
			cout << d[N] << '\n';
		}

		return 0;
	}