BOJ 33803 Lost Civilization

문제 링크입니다.

문제 요약

각 정점마다 요구되는 리프 노드까지 최소 거리가 주어집니다. 이를 만족하는 트리를 찾으세요.

풀이

리프 노드와의 거리가 가능한 먼 정점이 많도록 유도하는 게 최선입니다. 리프 노드의 개수를 최소화하는 식으로 접근했을 때 트리가 직선 형태인 경우가 최선이라고 유추해 볼 수 있습니다. 이게 맞는다면, 정점에 부여된 정수를 기준으로 오름차순 정렬했을 때 $i$번째 정점에 부여된 정수는 $\lfloor {i \over 2} \rfloor$ 이하여야 합니다.

이게 맞는지 확인해 봅시다. 그리디하게 매번 추가할 정점의 거리가 최대가 되도록 하면 최적해에 해당하는 트리의 구조를 알 수 있습니다. 일단 첫 두 정점은 반드시 리프 노드가 되고, 그 다음으로 추가하는 노드부터는 반드시 둘 이상의 정점과 인접해야 리프 노드가 아니게 됩니다. 이를 일반화하면, 거리가 $i+1$인 정점을 얻기 위해서는 거리가 $i$인 정점이 최소 두 개는 필요함을 알 수 있습니다.

트리가 직선형인 경우에, 우리는 항상 거리가 $i$인 정점이 두 개 생길 때마다 거리가 $i+1$인 정점을 뽑아낼 수 있으므로, 각 정점이 받을 수 있는 이론상 가장 큰 거리를 받게 됩니다. 따라서 직선형 트리가 최적해임이 보장되며, 직선형에서 정점 배치가 불가능하다면 답이 될 수 없습니다.

$N$의 홀짝성에 따라 잘 구현해 줍시다.

코드

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

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<pii> v;
	for(int i = 1; i <= n; i++){
		int a; cin >> a; v.emplace_back(a, i);
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < n; i++) if(v[i].first > i/2) return !(cout << "-1");
	for(int i = 0; i+2 < n; i+=2){
		cout << v[i].second << ' ' << v[i+2].second << '\n';
	}
	cout << v[n-2].second << ' ' << v[n-1].second << '\n';
	for(int i = (n%2 ? n-2 : n-1); i-2 >= 0; i -= 2){
		cout << v[i].second << ' ' << v[i-2].second << '\n';
	}
}