[백준] 3079. 입국심사 (Java)

안수진·2024년 9월 10일

Java 백준 이분탐색

Baekjoon

목록 보기

52/55

[BOJ] 3079. 입국심사

📌 풀이 과정

1. 이분 탐색을 활용하여 시간을 조정한다.

우리가 구하고자 하는 시간의 범위는 최소 1초부터 시작하여, 가장 오래 걸리는 심사관에게 모든 사람이 심사를 받을 경우의 시간인 최대 시간 = 가장 오래 걸리는 심사 시간 * 사람 수로 설정할 수 있다.

2. 주어진 시간 내에 모든 사람이 심사를 받을 수 있는지 확인합니다.

각 심사대에서 주어진 시간 동안 몇 명을 처리할 수 있는지를 계산하고, 이를 모두 더해 총 처리할 수 있는 사람의 수가 M명 이상인지를 확인한다.

3. 이분 탐색을 통해 최소 시간을 찾습니다.

시간 범위를 절반씩 줄여가며, 주어진 시간 내에 모든 사람을 심사할 수 있는지 확인한다.
가능한 경우에는 더 작은 시간을 시도하고,
불가능한 경우에는 더 큰 시간을 시도하여 최소 시간을 찾는다.

✨ 제출 코드

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;
    static long M, ans;
    static int[] desk;

    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()); // 상근이와 친구들

        desk = new int[N];
        int max = 0;
        for(int i = 0; i < N; i++) {
            desk[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, desk[i]);
        }

        Arrays.sort(desk); // 이분탐색을 위한 정렬
        ans = max * M; // 최대로 걸리는 시간 = 사람수 * 가장 오래 걸리는 심사 시간

        search();
        System.out.println(ans);

    }

    static void search(){
        long low = 1;
        long high = ans;

        while(low <= high){
            long mid = (low + high) / 2;
            long people = 0;
            
            for(int time : desk){ // mid 시간 내에 각 심사대에서 처리할 수 있는 사람의 수 계산
                people += mid / time;
                
                if(people >= M) break;
            }

            if(people >= M){ // 주어진 시간 내에 모든 사람을 처리할 수 있는 경우
                high = mid - 1; // 더 작은 시간을 탐색
                ans = mid;
            }
            else{
                low = mid + 1; // 더 큰 시간을 탐색
            }
        }

    }
}