BOJ(백준) 9460번 메탈

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

9460번: 메탈

매개 변수 탐색 + 그리디 알고리즘

문제 설명이 복잡하지만 간단하게 요약하면 다음과 같다.

 

2차원 좌표에서 x축에 평행한 선 k개를 서로 x좌표가 겹치지 않도록 그을 수 있는데 주어지는 점들 각각의 x좌표를 포함하는 선과 그 점 사이의 거리의 최대값이 가장 적어지도록  k개의 선을 그었을 때의 그 최대값을 구하는 문제이다.

 

매개 변수 탐색은 이분 탐색의 응용으로 내가 원하는 조건을 만족하는 값 중에서 최대값이나 최소값을 구하는 것이다.

이 문제에서는 다음과 같이 활용한다.

 

이 문제의 정답이 t라고 가정해보고 이것이 가능한지 살펴보자.

 

점들을 x좌표에 따라 정렬하고 앞에서부터 점들을 살펴보면서 점의 y좌표의 최대값과 최소값을 저장한다.

만약 최대값과 최소값의 차이가 2*t보다 크다면 이때는 이전까지의 점들을 하나의 선으로 커버하는 것이 불가능해진다.

따라서 선을 무조건 하나 더 그어야 한다는 것을 알 수 있다. 이후 다시 최소값과 최대값을 초기화한다.

 

이러한 과정을 반복하다가 만약 그어야 하는 선의 개수가 k개를 넘어간다면 정답은 t보다 크다는 것을 알 수 있고, 만약 k개 이하라면 정답은 t이하라는 사실을 알 수 있다.

 

이러한 방식을 반복하여 정답의 범위를 좁혀가며 조건을 만족하는 최소값을 찾는 것이 가능하다.

 

2*t는 경우에 따라 홀수이면  t가 소수가 될 수 있으므로 이러한 매개변수 탐색을 2*t값에 대해서 진행하면 된다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
int T,N,K,t1,t2;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout<<fixed;
	cout.precision(1);
	cin>>T;
	while(T--) {
		vector<pair<int,int>> v;
		cin>>N>>K;
		for(int i=0;i<N;i++) {
			cin>>t1>>t2;
			v.push_back({t1,t2});
		}
		sort(v.begin(),v.end());
		int s=0,e=200000000;
		while(s<=e) {
			int m=(s+e)/2,check=1,mx=-100000000,mn=100000000;
			for(auto i:v) {
				mx=max(mx,i.second);
				mn=min(mn,i.second);
				if(mx-mn>m) {
					check++;
					mx=mn=i.second;
				}
			}
			if(check<=K) e=m-1;
			else s=m+1;
		}
		cout<<(double)s/2<<"\n";
	}
}