(백준/C++) 1654_랜선 자르기

1654번: 랜선 자르기 (acmicpc.net) 문제는 이진 탐색(Binary search) 문제 중 파라메트릭 서치(Parametric search) 문제입니다.

Parametric Search란?

Parametric search는 이진 탐색(binary search)의 변형 중 하나로, 주로 최적화 문제를 결정 문제로 변환해 푸는 데 사용됩니다.

이 방식은 문제의 정답이 특정 범위 내에서 연속적인 값을 가질 때 유용합니다.

여기에서 결정 문제란, “예”, “아니오”로 답을 찾는 방식의 문제를 말합니다.

예를 들어, “5보다 큰 수 중 5에 가까운 수는?”을 주어진 배열에서 $N$번 수행하지 않고 이진 탐색을 통해 $logN$번 수행하는 문제로 바꿀 수 있습니다.

즉, 기존의 이진 탐색(binary search)이 특정 값을 찾기 위한 이진 탐색이라면, Parametric search는 특정 문제를 해결하기 위한 이진 탐색이라고 볼 수도 있을 것 같습니다.

---

접근법

1654번: 랜선 자르기 (acmicpc.net) 문제는 렌선 N개가 주어졌을 때, 이 렌선들을 자른 후에 M개 이상의 렌선을 얻기 위한 렌선의 최대 길이를 구하는 문제입니다

1) 범위 설정

이 문제는 Parametric Search를 사용하여 풀 수 있습니다. 렌선의 최소 길이는 1, 최대 길이는 주어진 렌선 중 가장 긴 것이므로 이 값을 범위로 잡고 이진 탐색을 하면 됩니다.

2) 이진 탐색

범위를 잡았다면, 중간 값부터 시작합니다. 이때, 현재 값을 가지고 각 렌선을 잘라보고 만들 수 있는 렌선의 개수를 비교해 봅니다.

• 현재 길이로 만들 수 있는 렌선이 부족하다면: 현재 길이가 길기 때문이므로 왼쪽으로 이진 탐색을 진행합니다.
• 현재 길이로 만들 수 있는 렌선이 많다면: 이미 정답에 가까워 졌지만, 더 최적 해가 존재할 수 있으므로 오른쪽으로 이진 탐색을 진행합니다.

이렇게 이진 탐색의 범위를 좁혀가며 탐색해 가다보면 최적의 답을 찾을 수 있는 방식이 Parametric search 입니다.

---

풀이

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

// 현재 사이즈로 만들 수 있는 렌선의 개수를 구합니다.
int cuttingLAN(const vector<int>& LANs, long long size)
{
	int result = 0;
	for(const int& LAN : LANs)
	{
		result += LAN / size;
	}
	return result;
}

// 해를 만족하는 최대 길이를 구합니다.
long long findLength(const vector<int>& LANs, int n)
{
	long long min = 1, max = *max_element(LANs.begin(), LANs.end());
	long long result = 0;

	while(min <= max)
	{
		long long mid = (min + max) / 2;
		int num = cuttingLAN(LANs, mid);

		if(num < n)
		{
			max = mid - 1; // 현재 길이로 만들 수 있는 렌선이 부족하다면 더 작은 길이로 탐색합니다.
		}
		else
		{
			result = mid;
			min = mid + 1; // 현재 길이로 만들 수 있는 렌선이 많다면 더 긴 길이로 탐색합니다.
		}
	}
	return result;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int K, N;
	cin >> K >> N;

	vector<int> LANs(K);
	for (int i = 0; i < K; i++)
		cin >> LANs[i];

	cout << findLength(LANs, N);
}