[백준] #3079. 입국심사 (골드 5)

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

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());  //입국심사대 수
		int m = Integer.parseInt(st.nextToken());  //사람 수
		int[] time = new int[n];  //입국심사대마다의 심사시간

		for (int i = 0; i < n; i++) {
			time[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(time);

		long low = time[0];
		long high = (long) time[n-1] * m;
		long minTime = 0;

		while (low <= high) {
			long mid = (low+high) / 2;
			long num = 0;  //사람 수
			for (long t : time) {
				num += mid / t;
				if(num >= m) break; // 통과해야되는 인원을 채웠으면 그만 추가하고 탈출
			}


			if (num >= m) {
				minTime = mid;
				high = mid - 1;
			}  else {
				low = mid + 1;
			}
		}
		System.out.println(minTime);

	}
}

 

주의할 점

1. 사람 수 num은 int가 아니라 long이어야 함

→ 심사를 하는데 걸리는 시간인 Tk의 범위 : 1 ≤ Tk ≤ 10^9 이므로 num은 int의 범위를 넘을 수 있기 때문

2. if(num >= m) break; // 통과해야되는 인원을 채웠으면 그만 추가하고 탈출

→ 위를 추가하여 num>=m일 때 반복문을 빠져나가 쓸데없이 연산을 계속 수행하는 것을 막아 오버플로우 막음