[백준/3079] - 입국심사(JAVA)

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력

---

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[] entry;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		entry = new int[N];
		for (int i=0; i<N; i++){
			entry[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(entry);
		long start = 0;
		long mid = 0;
		long end = 1000000000000000001l;
		while (start <= end){
			mid = (start + end) / 2;
			long count = 0;
			for (int i=0; i<N; i++){
				count += mid/entry[i];
				if (count > M) break;
			}
			//받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
			if (count >= M){
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		end = Math.min(end, mid);
		//최소 시간 출력
		System.out.println(end+1);
	}
}

해설

---

프로그래머스에 동일한 문제가 올라갈 만큼의 well-known한 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

이분탐색의 대표격인 만큼 다음 2가지는 꼭 알고 가야한다.

• Sorting
• 상한(Upper Bound)과 하한(Lower Bound)

소팅은 꼭 필요한 경우가 있고, 필요하지 않은 경우도 있다.

예를 들어,

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

1920번: 수 찾기

이런 '순서'가 문제 풀이의 핵심인 문제들은 반드시 소팅을 해야 한다.

그러나 '매개변수 탐색(Parametric Search)'과 같은, '순서'보다는 '크기'나 '개수'가 중요한 문제들은 소팅이 필요 없거나, 시간이 조금 더 단축된다. 나무 베기, 랜선 자르기 등과 같은 문제가 이에 해당한다.

 

상한과 하한은 문제를 해석할 때 다음을 생각해 보면 된다.

• 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치 => 하한
• 찾고자 하는 값 초과의 값이 처음으로 나타나는 위치 => 상한

다음 배열을 보자.

Arr =      | 1 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 9 |

index =    0   1   2   3   4   5   6   7   8

 

3 이상의 값이 처음으로 나타나는 인덱스 = 2

2를 초과하는 값이 처음으로 나타나는 인덱스 = 2

그래서 사실은 하한과 상한 둘 다의 방법으로 풀 수 있으나, 

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

10816번: 숫자 카드 2

위의 문제처럼 가끔은 하한과 상한 문제 두 가지 전부를 이용해서 풀어야 하는 문제도 존재한다.

각각을 위의 배열을 이용해 슈도 코드로 이용해서 나타내보자.

Arr =      | 1 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 9 |

index =    0   1   2   3   4   5   6   7   8

• 하한을 이용해 3 이상의 값이 처음으로 나타나는 구간

int start = 0;
int end = 8;
int target = 3;
while (start < end) {
	int mid = (start + end) / 2;
    if (target <= arr[mid]){
    	end = mid;
    } else {
    	start = mid + 1;
    }
}
return start;

• 상한을 이용해 3을 초과하는 값이 처음으로 나타나는 구간

int start = 0;
int end = 8;
int target = 3;
while (start < end) {
	int mid = (start + end) / 2;
    if (target < arr[mid]){
    	end = mid;
    } else {
    	start = mid + 1;
    }
}
return start;

물론, while 뒤에 start <= end를 함으로써 end를 mid - 1해줄 수도 있고, if 안의 조건을 바꿀수도 있다.

문제의 조건을 보고, '이분 탐색'이다 싶으면 이를 변경해주면 된다.

 

다시 문제로 돌아와서, 이 문제는 '최소한의 시간'으로 '주어진 만큼의 승객'을 받으면 된다.

따라서, count를 만족하는 최소한의 시간이므로 6명의 탑승객이 탑승해야 한다면

- 5명을 초과하는 최소의 시간(상한)

- 6명 이상인 최소의 시간(하한)

중 하나를 이용해 풀이하면 된다.

while (start <= end){
    mid = (start + end) / 2;
    long count = 0;
    for (int i=0; i<N; i++){
        count += mid/entry[i];
        if (count > M) break;
    }
    //받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
    if (count >= M){
        end = mid - 1;
    } else {
        start = mid + 1;
    }
}
end = Math.min(end, mid);
//최소 시간 출력
System.out.println(end+1);

처음에 시간을 최대한으로 많이 잡아놓고,

각각의 카운터를 배열로 설정한다.

카운터 1번이 입국심사를 받는 데 7분이 걸리고, 카운터 2번이 입국심사를 받는데 10분이 걸린다면

28분이 주어질 경우 1번 카운터는 4명, 2번 카운터는 2명을 받을 수 있게 된다.

시간 절약을 위해 count > M을 하면 자동으로 반복문을 빠져나가 다시 이분탐색을 할 수 있게끔 하였다.

그래서 결국 6명을 받을 수 있는 최소한의 입국심사 시간을 찾아서 리턴하게 되는 것이다.