[SWEA] 입국심사

[3074] 입국심사

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_XEokaAEcDFAX7

 

 

 

Solution

• 이분 탐색으로 푸는 문제였다. (몰랐다)
• 전체 입국심사에 걸리는 최악의 시간 = (가장 오래걸리는 입국심사대 시간) * (대기자 수)
• 따라서 [0 ~ 최악의 시간]을 최초 범위로 잡고 이분 탐색으로 범위를 좁혀가며 최소 시간을 구한다.

 

 

소스코드

import java.util.Scanner;
 
public class Solution {
    static int N, M;
    static long[] arr;
    static long maxTime;
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
 
        int tnum = input.nextInt();
 
        for (int t = 1; t <= tnum; t++) {
            N = input.nextInt();
            M = input.nextInt();
 
            arr = new long[N];
            maxTime = 0;
            for (int i = 0; i < N; i++) {
                arr[i] = input.nextInt();
                if (arr[i] > maxTime) {
                    maxTime = arr[i];
                }
            }
 
            System.out.println("#" + t + " " + binarySearch(0, maxTime * M));
        }
    }
 
    private static long binarySearch(long start, long end) {
 
        long min = maxTime * M;
 
        while (start <= end) {
            long target = 0;
 
            long mid = (start + end) / 2;
            for (int i = 0; i < arr.length; i++) {
                target += mid / arr[i];
            }
 
            if (target < M) {
                start = mid + 1;
            } else {
                if (min > mid) {
                    min = mid;
                }
                end = mid - 1;
            }
        }
        return min;
    }
 
}