[알고리즘] 백준 3079번: 입국심사 (C++), 이분탐색이라는 전제가 없었다면 풀 수 있었을까

이번 문제는 이분 탐색이라는 전제가 없었다면 풀 수 없었을 것이다.

이분 탐색이라는 전제가 있어도 논리에 접근하기 까다로운 문제였다.

 

걸리는 시간을 여러 값으로 추정하며 이분 탐색으로 도달하는 문제다.

---

논리에 접근했던 방법

처음엔 최소 시간이 걸리는 검색대에 사람들이 몰리게 해야겠다는 생각이 들었다.

>> 검색대의 시간들을 배열에 담아 정렬시켰다.

 

그래서 걸리는 시간(mid)이 주어지면 그 시간 안에 최소 시간 검색대에 몇 명의 사람이 올 수 있는지 카운트해주었다.

>> sum을 선언하고 sum이 mid가 될 때까지 걸리는 시간을 더해준 후에 mid가 되면 다음 시간 검색대에서 같은 과정을 반복해주었다.

for (int i = 0; i < times.size(); i++) {
	ll sum = 0;
	while (sum <= mid) {
		sum += times[i];
		cnt++;
	}
	cnt--; // sum이 mid를 초과했을 때도 한 번 cnt되어서
}

 

그리고 난 뒤에 cnt(사람의 수)가 많다는 것은 시간을 더 좁혀서 주어진 사람의 수(m)에 도달하게끔 점점 좁혀가야 한다. 

if (cnt < m) {
	low = mid + 1;
}
else {
	high = mid - 1;
	answer = mid;
}

 

하지만 이와 같은 논리는 시간 초과를 발생시킨다. (논리가 틀렸다는 말은 아님)

극단적인 예로는 다음과 같다.

1 1000000000
1000000000

이 경우에 이 코드에서 sum에 걸리는 시간(times[i])을 더해주는 것이 시간을 엄청 잡아먹기 때문이다.

for (int i = 0; i < times.size(); i++) {
	ll sum = 0;
	while (sum <= mid) {
		sum += times[i];
		cnt++;
	}
	cnt--; // sum이 mid를 초과했을 때도 한 번 cnt되어서
}

 

>> 하나씩 더해갈 필요 없이 나눠준 몫이 똑같은 값이라는 생각이 들어서 코드를 다음과 같이 바꿔주었다.

for (int i = 0; i < times.size(); i++) {
	cnt += mid / times[i];
}

 

+ 시간 초과 문제와 더불어 자료형 문제도 있었다. (int -> unsigned long long으로 전환하면 끝나는 문제였다.)

---

논리

이번 문제는 위에서 말했듯이 이분 탐색이라는 키워드가 주어지지 않았다면 시간이 더 오래 걸렸다거나 못 푸는 문제였을 것이다. 그와 더불어 문제에서 (1초를 더 기다리고...)와 같은 말에서 '이게 이분 탐색으로 가능할까'라는 생각을 했다. 문제에 혼란을 줄 수 있는 말이었다. 예제 입력과 출력(테스트 케이스)을 보고 접근을 했던 거 같다. ('8초가 주어지면 그 안에 계산할 수 있는 최솟값 => 값이 주어진다? == 이분 탐색' 이런 식으로)

 

맨 위에 논리를 접근했던 방법에서 최소 시간이 걸리는 검색대에 사람들이 몰리게 해야겠다고 생각할 수 있었던 건 문제 자체를 검색대로 보지 않고 노트에 적으면서 검색대라는 키워드보다 숫자로서 접근할 수 있었다.

 

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll unsigned long long

vector<ll> times;

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		ll time;
		cin >> time;
		times.push_back(time);
	}

	sort(times.begin(), times.end());

	ll low = 0;
	ll high = times.back() * m; // 제일 시간이 긴 탐색대에 다 몰리는 경우
	ll answer = 0;

	while (low <= high) {
		ll mid = (low + high) / 2;
		ll cnt = 0; // 역할: 사람 세는 것

		for (int i = 0; i < times.size(); i++) {
			cnt += mid / times[i];
		}

		//cout << mid << ' ' << low << ' ' << high << '\n';

		if (cnt < m) {
			low = mid + 1;
		}
		else {
			high = mid - 1;
			answer = mid;
		}
	}

	cout << answer;
	return 0;
}