취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27296번 문제인 카탈란 마스터의 선분 그리기 게임이다.
문제는 아래 링크를 확인하자.

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

점이 3개 이상인 경우를 생각해보자. 그 외의 경우 답은 예제 출력과 같다.

원주를 따라 놓여있는 점들을 차례대로 이으면 볼록$N$각형을 얻을 수 있다. 이 볼록$N$각형의 각 변은 언제 그어도 다른 모든 선분과 교차하지 않으므로 이러한 $N$개의 선분은 항상 그을 수 있다.

그 외의 선분은 하나를 그을 때마다 위의 볼록$N$각형을 작은 다각형으로 분할하는 모양새를 띄게 되는데, 이것이 가능할 때까지 계속 선분을 그으면 결국 볼록$N$각형의 삼각분할(Triangulation)을 얻게 된다. 이 과정에서 긋게 되는 선분은 항상 $N-3$개이다.

따라서 $N$이 주어지면 항상 $2N-3$개의 선분을 긋게 됨을 알 수 있다. 이를 통해 게임의 승패를 구하고 문제를 해결하자.

지문의 카탈란 수 언급이 함정이라는 기여 의견이 보여 주관적인 생각을 같이 적어둔다. 지문에서 삼각분할이라는 표현을 직접 제시하지 않았을 뿐 카탈란 수를 직접 언급하고 있으므로 카탈란 수와 삼각분할의 관계를 알고 있는 사람이라면 매우 쉽게 풀 수 있는 문제라고 생각한다. 배경 지식을 쌓는 것을 게을리 하지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int T;
ll N;

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

	cin >> T;
	while (T--) {
		cin >> N;
		if (N < 2) cout << "1 0\n";
		else cout << "0 1\n";
	}
}