[BaekJoon] 3079 입국심사 (Java)

1.  문제 링크

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

2.  문제

요약

• 상근이와 친구들은 총 M명이고, 입국심사대는 총 N개가 있습니다.
• k번 심사대에 앉아있는 심사관이 한 명을 심사하는데 드는 시간은 $T_k$입니다.
• 가장 처음에 모든 심사대는 비어있고, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들입니다.
• 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있고, 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있으나 항상 이동을 해야 하는 것은 아닙니다.
• 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 됩니다.
• 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 N과 1보다 크거나 같고 1,000,000,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 N개의 줄에는 1보다 크거나 같고 $10^9$보다 작거나 같은 $T_k$가 주어집니다.
• 출력: 첫 번째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public long getMinTime(int people_num, int[] immigration_time) {
		int max = 0;
		for(int i = 0; i < immigration_time.length; i++) {
			if(max < immigration_time[i]) {
				max = immigration_time[i];
			}
		}
		long left = 0L;
		long right = max * 1000000000L;
		long time = 0L;
		while(left <= right) {
			long mid = (left + right) / 2;
			long count = 0;
			for(int i = 0; i < immigration_time.length; i++) {
				count += (mid / immigration_time[i]);
			}
			if(count >= people_num) {
				time = mid;
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}
		return time;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int immigration_num = Integer.parseInt(input[0]);
		int people_num = Integer.parseInt(input[1]);
		int[] immigration_time = new int[immigration_num];
		for(int i = 0; i < immigration_num; i++) {
			immigration_time[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinTime(people_num, immigration_time) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 이진 탐색을 이용하여 해결할 수 있는 문제입니다.
• 특정 시간에 입국 심사대에서 통과시킬 수 있는 사람 수의 최댓값을 구하여 이를 바탕으로 이진 탐색을 진행합니다.
• 최솟값인 0과 최댓값인 ($T_k$ 중 최댓값) * 1000000000(심사 받는 사람 수의 최댓값)을 각각 left와 right로 두고 탐색을 시작합니다.
• (left + right) / 2 값인 mid에 대해서 만약 mid초에 m명 이상의 사람을 입국 심사대로 보낼 수 있다면 m명 이상 통과시키는 시간은 최소 시간이 되지 않기 때문에 값을 줄이기 위해 right 값을 mid - 1로 변경합니다.
• 만약 mid초에 (m - 1)명 이하의 사람을 입국 심사대로 보낼 수 있다면 총 m명을 통과시켜야하므로 조건에 맞지 않아 값을 키우기 위해 left의 값을 mid + 1로 변경합니다.

1. 주어진 $T_k$들을 1차원 배열 immigration_time에 넣어주고 그 값들 중에서 최댓값을 변수 max에 넣어줍니다.
2. left 변수에 시간의 최솟값인 0을 넣어주고 right 변수에 시간의 최댓값인 max * 1000000000을 넣어주며 심사를 마치는데 걸리는 시간의 최솟값을 나타내는 변수 time을 생성하고 값을 0으로 초기화합니다.
3. left가 right보다 작거나 같을 때까지 반복문을 돌며 심사를 마치는데 걸리는 시간의 최솟값을 구합니다.
   1. left와 right의 중간값을 mid에 넣어줍니다.
   2. mid초에서 각 입국 심사대에 통과시킬 수 있는 사람의 수의 합을 나타내는 변수 count를 생성하고 값을 0으로 초기화합니다.
   3. 각 입국 심사대에 대해 반복문을 돌며 mid초에서 각 입국 심사대에 통과시킬 수 있는 사람의 수를 구합니다.
      • mid / (현재 입국 심사대의 $T_k$)를 구하고 이 값을 count에 더해줍니다.
   4. 만약 count 값이 통과시키려는 사람의 수 people_num보다 크거나 같다면 time의 값을 mid로 설정하고 right의 값을 (mid - 1)로 변경해줍니다.
   5. 만약 그렇지 않다면 left의 값을 (mid + 1)로 변경해줍니다.
4. 3번의 반복문이 끝났을 때의 time값이 심사를 마치는데 걸리는 시간의 최솟값이므로 이를 출력합니다.