백준 1654. 랜선 자르기

랜선 자르기

이진 탐색 문제의 응용 버전, 파라메트릭 서치(매개 변수 탐색) 문제

1. 간단 설명

---

K개의 각각의 다른 길이를 가진 랜선이 있다

랜선을 모두 같은 길이로 잘라서 N개를 만들어야한다

가지고 있는 랜선 개수 K, 필요 랜선 개수 N이 주어지고

K 줄에 걸쳐 이미 가지고 있는 랜선의 길이가 센티미터 단위 정수로 주어짐

N개를 만들 수 있는 랜선의 최대 길이를 구하기

2. 예제

---

ex1)

4 11
802
743
457
539

4개의 랜선 802cm, 743cm, 457cm, 539cm가 있음

이를 적당히 잘라서 11개의 같은 길이를 가지는 랜선을 만들어야한다

각각 200cm씩

802cm에서 4개, 743cm에서 3개, 457cm 에서 2개, 539cm에서 2개 자르면

총 11개를 만들 수 있다

ex2)

2 3
1 
10 

2번째 10cm 케이블에서 3cm 씩 3개 자를 수 있음

ex3)

2 2
2147483645
2147483645

랜선 최대 길이인 2,147,483,645cm 랜선 두개로 두개를 만들어야한다

2,147,483,645cm 두개를 그냥 가져오면 되므로, 최대 길이는 2,147,483,645cm 가 된다

이분탐색 시 덧셈 과정에서 오버플로에 주의해야 할 예제

3. 알고리즘

---

첫번째 시도

가장 먼저 떠오른 아이디어는

1. 가장 작은 길이의 전선 크기 만큼 잘라본다
2. N개가 만들어지는지 체크
3. 모자르다면, 가장 작은 전선의 길이를 절반으로 나눈 범위로 시도
4. N개가 만들어지는지 체크
   • 만들어진다면 mid값 다시 설정 후 시도
   • 안만들어진다면 또 절반으로 나눠봄

위 방법으로 시도했으나, 시간초과

2 2
1 1000

다음과 같은 경우를 처리하지 못한다

위의 알고리즘은 1cm 씩 2개가 나오는데 정답은 500cm 씩 두개 자를 수 있음

두번째 시도

Parametric search

• 파라메트릭 서치, 매개 변수 탐색이라 불리는 알고리즘 사용
• 결정 문제로 변환하여 해결하는 이진 탐색 기반의 알고리즘이다
• 이분 탐색은 정렬된 배열에서 특정한 값을 찾는 용도로 사용하지만
• 파라메트릭 서치는 가능한 해의 최적값을 찾는 과정에서 이진 탐색을 활용하는 알고리즘이다

파라메트릭 서치의 핵심 아이디어

1. 최적 해가 특정 범위 내에 존재한다
   • L, R 혹은 Low, High 사이에 정답이 있다고 가정
2. “이 값으로 조건을 만족할 수 있는가” 라는 결정 문제를 설정함
   • 이를 해결하는 함수 is_possible(mid)를 구현한다
3. 이진 탐색을 수행하며 최적의 값을 찾는다
   • mid = (low + high) / 2 로 설정하고
   • is_possible(mid) == ture 라면, 더 나은 해를 찾기 위해 mid를 조정한다

위의 문제에 이를 적용해보면

1. 최적의 랜선 길이가 `(1, 최대 랜선 길이)` 사이에 무조건 존재한다
2. `mid = (1 + MAX) / 2`로 세팅 후 `is_possible(mid)` 에 넣어본다
3. 조건을 만족한다면, 더 길게 잘라도 되므로 low 값을 mid + 1 로 세팅 후 재시도
4. 만족하지 못한다면, 더 짧게 잘라야 하므로 high 값을 mid - 1로 세팅 후 재시도
5. low 값이 high 값 이상이라면 종료한다

4. 소스코드

---

#include <iostream>
#include <vector>

using namespace std;

int K, N;
vector<int> v;
unsigned long long int res;

void my_binary_search(unsigned long long int low, unsigned long long int high) {
	int result = -1;

	while (low <= high) {
		unsigned long long int mid = (low + high) / 2;
		unsigned long long int cnt = 0; // 자를 수 있는 랜선 개수
		for (int e : v) {
			cnt += e / mid;
		}

		if (cnt >= N) {
			low = mid + 1;
			if (res < mid) res = mid;
		}
		else {
			high = mid - 1;
		}
	}

	return;
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> K >> N;
	v.resize(K);
	int high = 1;
	for (int i = 0; i < K; i++) {
		cin >> v[i];
		if (v[i] > high) high = v[i];
	}

	my_binary_search(1, high);

	cout << res;

	return 0;
}

이분 탐색은 몇번 풀어봤지만, 이를 이용해 최적의 값을 찾는 문제를 처음 풀어보았다

이런 알고리즘을 파라메트릭 서치라고 부르는걸 배웠다

또한, 이분 탐색 시, int형으로 변수를 설정할 때

언제 오버플로우가 나는지 알 수 있어서 좋은 문제였다고 생각한다