[3079] 입국심사

 

3079번: 입국심사

 
이분 탐색 문제다.
이분 탐색 카테고리가 없었다면 이분 탐색이라는 방법을 쓸 생각을 못 했을 것 같다. 아마 각 줄에 몇 명이 있어야하는지 알고리즘이 딱히 없었기 때문에 모든 시간을 탐색해서 확인하는 방법이 필요했을 것이다. 그 과정에서 시간은 순차적이기 때문에 이분 탐색이어야만 했다.
 
주어진 시간동안 각각의 줄에서 처리할 수 있는 사람의 수를 구해 그 사람의 수가 M보다 큰지 작은지 확인해 범위를 좁혀나간다. 스케줄 표를 작성하는 게 아니라 시간만 확인하면 되기 때문에 누가 어디에 들어갔는지는 굳이 신경써도 되지 않아도 됨! 과정에서 M의 최대값은 10^9, N의 최대 값은 10^5이기 때문에 이분 탐색 시 범위가 int를 초과한다. 따라서 long long타입을 써야 오류가 나지 않는다.
 
단 의문인 점은 계산 시간을 줄이기 위해 사람 수를 구하는 과정에서 M이 초과되면 break를 걸어줄 때 break를 걸어주지 않는다면 오류가 난다. 답과 관련된 건 아닌 것 같은데 왜 오류가 나는지 모르겠다. 아시면 답좀. 그리고 해당 문제를 찾아보다가 다른 블로그 글의 코드를 돌려봤는데 거진 전부 32%즘에서 틀렸다고 떴다. 뭔가 답이 틀려졌나..?

 

(++ 추가

프로그래머스에서도 같은 문제가 있어서 풀어봤다. 프로그래머스에서는 break를 걸어주지 않아도 괜찮음. 대신 주의해야할 점이 있는데 max_time이 long long type이라 M * max_time할 때 int * int 곱이 되지 않는지 확인해줘야 한다. int끼리의 곱은 int형식으로 계산 되기 때문에 long long으로 들어가더라도 int형식으로 들어간다.

 

다시 말해 M과 max_time의 곱이 int 범위를 넘어서면 long long으로 자동 변환되는 게 아니라 int 범위 그대로 들어가기 때문에 범위가 잘린다.

#include <iostream>

using namespace std;

typedef long long ll;
int main() {
	ll N, M;
	cin >> N >> M;

	ll time[100001];
	ll max_time = 0;

	for (int i = 0; i < N; i++) {
		cin >> time[i];

		if (max_time < time[i]) max_time = time[i];
	}

	ll start = 1;
	ll end = M * max_time;

	while (start <= end) {
		ll middle = (start + end) / 2;
		ll tmp = 0;

		for (int i = 0; i < N; i++){
			tmp += (middle / time[i]); // i번째 창구에서 middle 시간동안 처리할 수 있는 사람의 수
            if (tmp >= M)
                break;
        }

		if (tmp >= M) end = middle - 1; // 처리할 수 있는 사람보다 많으므로 시간을 줄임
		else start = middle + 1;
            
	}

	cout << start;
}