취미로 코딩하기

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

이번에 볼 문제는 백준 9460번 문제인 메탈이다.
문제는 아래 링크를 확인하자.

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

주어진 금속을 전부 채굴하기 위한 최소비용을 구하는 문제이다.

금속의 총 채굴 비용 cost가 고정된 값으로 주어진다면 이 때 필요한 최소 수평터널의 개수를 구하는 것은 그리디한 방식으로 구해낼 수 있음을 관찰하자. 또한, cost가 증가하면 필요한 최소 수평터널의 개수는 단조감소하는 관계가 있음을 관찰하자.

위의 관찰을 이용해 총 채굴비용으로 가능한 값의 범위를 처음에는 전체 범위로 잡고 이진탐색을 통해 단계마다 절반씩 줄여나가 문제를 해결하자.

문제의 답은 항상 .0 또는 .5와 같은 소수점 한자리로 떨어지는, 즉 정수 혹은 정수의 절반꼴로 떨어짐을 관찰해 이진탐색을 부동소수점 범위까지 할 필요 없게끔 적절히 조절할 수 있다. 값이 그렇게 떨어지는 이유는 각 터널에서 채굴할 수 있는 가장 높은 위치의 금속과 낮은 위치의 고저차가 정수로 떨어진다는 점을 관찰해 알아낼 수 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T;
int N, K;
pair<int, int> points[10000];

int func(int x) {
	int ret = 1;
	int rangeL = points[0].second - x, rangeR = points[0].second + x;
	for (int i = 1; i < N; i++) {
		int tmpL = points[i].second - x, tmpR = points[i].second + x;
		if (rangeR < points[i].second || points[i].second < rangeL) ret++, rangeL = tmpL, rangeR = tmpR;
		else rangeL = max(rangeL, tmpL), rangeR = min(rangeR, tmpR);
	}

	return ret;
}

void solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;
	sort(points, points + N);

	int L = 0, R = 200000000;
	while (L < R) {
		int mid = (L + R) / 2;
		if (func(mid) <= K) R = mid;
		else L = mid + 1;
	}

	if (L & 1) cout << L / 2 << ".5\n";
	else cout << L / 2 << ".0\n";
}

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

	cin >> T;
	while (T--) solve();
}