[G4] 백준 16766번 Convention C++ 이분 탐색, 매개 변수 탐색

리뷰

 

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

모든 소를 버스로 나를때 가장 오래 기다린 소의 대기시간의 최대값이 가장 작은 케이스를 찾는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 소의 개수를 저장할 변수
• m : 버스의 개수를 저장할 변수
• c : 버스에 최대한 태울 수 있는 소의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, m, c값을 입력 받고, 변수 l, r을 모두 0으로 초기화한다.
2. n마리의 소의 도착시간을 입력 받아 arr배열을 초기화하고, 최대 도착 시간을 변수 r에 저장한다.
3. sort함수를 통해 arr배열을 오름차순으로 정렬한다.
4. 변수 ans를 매우 큰 값으로 초기화한다.
5. 매개변수 탐색을 통해 m개의 버스에서, 한 버스당 최대 c마리의 소를 운반하며 소의 대기시간이 가장 작은 케이스를 찾아 ans에 저장해준다.
6. ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. 버스가 정원 초과되는 분기 처리를 할때 in_bus > c로 검증하여 WA를 받았다.
2. in_bud >= c로 분기처리를 변경해주어 AC를 받았다.

 

참고 사항

1. M*C가 N이상임이 보장된다.
2. 풀고 나서 느꼈지만 사실상 mid의 최대값을 구하는 문제랑 동일해보인다.

 

정답 코드

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

const int N = 1e5;
int n, m, c;
int arr[N];

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

	cin >> n >> m >> c;
	int l = 0, r = 0;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
		if (r < arr[i]) r = arr[i];
	}
	sort(arr, arr + n);

	int ans = 2e9;
	while (l <= r) {
		int mid = (l + r) / 2;
		int arrive = arr[0];
		int cnt = 1;
		int in_bus = 1;
		int mx = 0;

		for (int i = 1; i < n; ++i) {
			if (cnt > m) break;
			if (arrive + mid < arr[i] || in_bus >= c) {
				mx = max(mx, arr[i - 1] - arrive);
				in_bus = 1;
				arrive = arr[i];
				++cnt;
				continue;
			}
			++in_bus;
		}
		mx = max(mx, arr[n - 1] - arrive);

		if (cnt > m) l = mid + 1;
		else {
			ans = min(ans, mx);
			r = mid - 1;
		}
	}
	cout << ans;
}