BOJ 28240 S리그

문제 링크입니다.

문제 요약

길이 $N$의 사이클에 최대 두 개의 서로 정점을 공유하지 않는 간선이 추가된 그래프를 간선끼리 교차하지 않도록 평면 위에 올리세요.

풀이

사이클 대신 $1$번과 $N$번 정점 간의 연결이 없는 선형적 구조를 생각해 봅시다. 이 정점들을 일렬로 쭉 나열해 보면, 추가된 두 개의 간선이 연결된 네 개의 정점을 각각 해당 선의 양 옆에 그린 뒤 이어주면 모든 간선이 서로 겹치지 않고 한 평면 위에 배치된다는 사실을 발견할 수 있습니다.

이제 $N$번 정점과 $1$번 정점을 연결하면 되는데, $N$번 정점이 혼자 정점을을 늘어놓은 기준선에서 엄청나게 멀리 떨어져 있으면 나머지 정점에 간선을 원하는 대로 쏠 수 있을 거라 생각해 볼 수 있습니다. 실제로도 그러하니, $N$번 정점에 추가된 간선이 붙음에 따라 방향이 고정되는 경우만 조심해서 슥슥 구현해주면 총 시간 복잡도 ${\cal O}(N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	int a, b, c, d; cin >> a >> b >> c >> d;
	for(int i = 1; i <= n-1; i++){
		cout << i << ' ';
		if(i == a || i == b) cout << 1;
		else if(i == c || i == d) cout << -1;
		else cout << 0;
		cout << '\n'; 
	}
	cout << n << ' ';
	if(n == a || n == b) cout << 2*n;
	else cout << -2*n;
}