BOJ 3079 - 입국심사

 

 

문제

 

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

3079번: 입국심사

 

• 상근이와 친구들 M명 (1 ≤ M ≤ 10억)
• 입국심사대 N개 (1 ≤ N ≤ 10만)
• k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk (1 ≤ Tk ≤ 10억)
• 모든 사람이 심사를 받는데 걸리는 시간이 최소가 되도록

 

아이디어

' 최소 '라는 키워드가 나와서 이분탐색으로 먼저 접근해보았다.

 

 

원래 문제

N개의 심사대에 M명의 사람이 심사받을 때 모든 사람이 심사를 받는데 드는 최소 시간은?

 

최소 시간을 매개 변수 T로 설정하고 문제를 뒤집어서 Yes or No 결정 문제로 만든다.

 

뒤집어서 만든 Yes or No 문제

최소 시간 T일 때 N개의 심사대에서 M명의 사람이 심사받을 수 있는가? Yes or No?

 

이분탐색

이분 탐색으로 T를 찾는다. 범위는 각 심사대에서 걸리는 시간의 최솟값부터 10억명의 사람을 10억시간 걸리는 심사대에서 다 검사했을 때, 즉 최대로 걸릴 수 있는 시간인 10억*10억까지이다. 이분 탐색을 진행해 Yes or No를 채운 후 최소값을 찾아야 하므로 처음으로 나온 Yes를 찾는다.

 

당연히 탐색 범위가 int 범위를 초과하니까 long으로 변수를 설정해야 할 것!

 

Yes or No 문제 풀이

시간이 T로 주어졌을 때 그 시간 안에 N명이 M개의 검색대에서 검사가 가능한 지를 확인한다. T로 각 검색대의 시간을 나눈 값을 더해줘서 그게 M명과 같은지 확해주면 된다.

 

 

시간 복잡도

• Yes or No 문제 풀 때 최대 O(10만)
• 이분 탐색 시 범위가 10억*10억이므로 약 O(log 10^18)
• 총 O(10만 * log 10^18)이므로 1초안에 풀이가 가능하다.

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] time;

    static void init() 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());

        time = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            time[i] = Integer.parseInt(br.readLine());
        }
    }

    static void pro() throws IOException {
        // 탐색 범위가 크므로 long으로 초기화
        long L = Integer.MAX_VALUE;
        long R = Integer.MIN_VALUE;
        
        // L과 R을 가능한 최소, 최대값으로 범위 설정
        for (int i = 1; i <= N; i++) {
            L = Math.min(L, time[i]);
            R = Math.max(R, time[i]);
        }
        R *= M;

        long ans = 0;

        // 이분탐색
        while (L <= R) {
            long mid = (L + R) / 2;

            if (YesOrNo(mid)) {
                // 최소를 구해야 하므로 가장 먼저 나온 Yes 찾기
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }

        bw.write(ans+" ");
    }

    // 주어진 시간 T동안 M명이 모두 검사가 가능한가? Yes or No? 
    static boolean YesOrNo(long T) {
        long cnt = 0;

        // 주어진 시간 안 검사 가능한 최대 인원 구해주기  
        for (int i = 1; i <= N; i++) {
            cnt += T / time[i];
        }

        // M과 비교
        return cnt >= M;
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}