[백준] 3079 - 입국심사 by C++

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

3079번: 입국심사

전형적인 이분탐색 문제였다. 이분탐색을 제대로 이해하질 못해서, 이 문제를 통해 원리를 어느정도 이해할 수 있었다.

 

알고리즘 방식

이분 탐색의 대상은 상근이와 친구들이 심사를 마치는데 걸리는 시간이였다. (즉 정답)

시작값(st) = 0, 끝값(en) = Tk의 최대값 * M으로 지정해주었다.

(시작값 또한 Tk의 최소값 * M으로 지정해도 되지만, 의미 없는 것 같아 생략)

 

1. 선택된 시간(mid)에서 통과할 수 있는 사람의 최대값(sum)을 구한다.

2. 최대값이 M보다 작다면, mid 값을 키워야하므로 st = mid + 1

    최대값이 M보다 크거나 같으면, mid 값을 줄여야 하므로 en = mid - 1;

3. 구해진 en 값은 정답보다 -1작은 수이므로, (en = mid - 1인 상태로 while문을 탈출하기 때문)

    en + 1을 정답으로 출력한다.

 

 

고찰

void Solution() {
	long long st = 0, en = maxT * M;
	long long answer;
	while (st <= en) {
		long long mid = (st + en) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			sum += mid / Tk[i];
		}
		//1.sum == M 인 경우의 최솟값
		if (sum < M) {
			st = mid + 1;
		}
		else {
			answer = mid;
			en = mid - 1;
		}
		
		//2.sum == M 인 경우의 최댓값
		//if (sum > M) {
		//	en = mid - 1;
		//}
		//else {
		//  answer = mid;
		//	st = mid + 1;
		//}
	}
}

이 문제의 예제 1을 통해 이해해보겠다.

먼저 sum == M일 수 있는 값의 범위는 28 ~ 29 이다.

1. sum == M 인 경우의 최솟값

아래 두 가지 경우는 서로 독립적이다. (while 문을 탈출할 때, 아래 두가지 조건이 만족하지 않기 때문)

1. st는 반드시 28에서 멈춘다. (sum < M 을 만족하는 마지막 수는 27이고, 이 값에 +1한 28을 st에 대입하기 때문)

2. en는 반드시 27에서 멈춘다. (sum >= M을 만족하는 마지막 수는 28이고, 이 값에 -1한 27을 en에 대입하기 때문)

그렇기 때문에, 정답은 st, en + 1모두 가능하다.

 

2. sum == M 인 경우의 최댓값

아래 두 가지 경우는 서로 독립적이다. (while 문을 탈출할 때, 아래 두가지 조건이 만족하지 않기 때문)

1. en는 반드시 29에서 멈춘다. (sum > M 을 만족하는 마지막 수는 30이고, 이 값에 -1한 29을 en에 대입하기 때문)

2. st는 반드시 30에서 멈춘다. (sum <= M 을 만족하는 마지막 수는 29이고, 이 갑셍 +1한 30을 st에 대입하기 때문)

 

위 두가지 경우를 이해하면, 이분 탐색 문제에서 해당 조건을 만족하는 최댓값, 최솟값을 유연하게 선택하여 문제를 풀이할 수 있을 것 같다.

 

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> Tk;
long long maxT;

void Solution() {
	long long st = 0, en = maxT * M;
	while (st <= en) {
		long long mid = (st + en) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			sum += mid / Tk[i];
		}

		if (sum < M) {
			st = mid + 1;
		}
		else {
			en = mid - 1;
		}

	}
	cout << en + 1;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> M;

	int input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		Tk.push_back(input);
		if (input > maxT)
			maxT = input;
	}

	Solution();
}