[java] 3079번 입국심사

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

처음에 문제 읽으면서 dp인가 ~~ 했는데
범위보고 입 벌어짐 => 1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000
이분탐색 문제였다.

start = 1, end = (심사대 소요 시간 중 Max값)*사람수 로 두고
mid 값을 조정해주면서 소요 시간을 찾는다.

• 심사끝난 사람 수가 M 보다 크면 end = mid -1
• M보다 작으면 start = mid +1

심사끝난 사람 수 어떻게 계산?

			for(int i=0;i<N;i++){
				sum += (mid/timeArr[i]);
				// if (sum >=M ) break;
			} 

mid/timeArr[i] 는 현재시간/소요시간 으로,
현재시간= 10, timeArr= [1,5,10] 이라고 가정했을 때
10/1 = 10 => 10명 가능
10/5 = 2 => 2명 가능
10/10 = 1 => 1명 가능

처음에 코드보고 아💡 이게 안와서 정리해보겠다.
백준예시 2

소요 시간 수는 TimeArr 로 받아, sort() 하여 표시하였습니다

1. start =1 .end = 최대 소요 시간 9 * 탑승승객 수 10=> 90 , mid = (start+end)/2= 45

우리는 10명만 태우면 되는데, 80 이므로 end = mid - 1 을 해준다 .. end=44

2. 37명도 많다. end = mid-1

3. end = 21 (과정 생략), 다음 end = 10

어라, 10명 태워야 하는데 승객 수가 5명이네. 그럼 start = mid + 1 = 6

4. start = 6 , end=10
   탑승수 12 이므로, end = mid -1

5. start = 6, end = 7, 탐승수 9명이므로 start = mid + 1

6. start=7, end = 7 마지막이라 mid/timeArr[i] 연산도 적어보았다.
   탑승수 9명이므로, start = mid+1

7. start가 end를 넘었으므로, print(start)
   start = 8 일 때, 즉 8초가 소요될 때도 계산해보자면 12가 나온다.
   7초가 소요될 때 9명 이었으므로 10명 못태우니,
   그 다음 최솟값인 8이 정답이 맞다!
   

3. 코드

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

public class Main {

	static int N, M;
	static int[] timeArr ;
	static int MaxTime = 0 ;

	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());
		timeArr = new int[N];
		for(int i=0;i<N;i++){
			timeArr[i] = Integer.parseInt(br.readLine());
			MaxTime = Math.max(MaxTime, timeArr[i]);
		}

		Arrays.sort(timeArr);

		long start = 1;
		long end = (long) MaxTime * M ;
		
		while (start <= end){
			long mid = (start+end)/2;

			long sum = 0;
			for(int i=0;i<N;i++){
				sum += (mid/timeArr[i]);
				if (sum >=M ) break;
			} 

			if(sum >=M) end = mid - 1;
			else start = mid + 1;
		}
		System.out.println(start);
	}
}