[백준] 3079 입국 심사 (java)

 

백준 3079번 입국심사 자바 풀이

---

 

 

 

3079번: 입국심사

 

 

문제 3줄 요약

 

여러명의 사람들이 여러개의 입국심사대에서 심사를 받는다.

 

입국심사대는 각각 정해진 심사 시간이 있다.

 

가장 빨리 사람들이 모두 입국심사를 받을 수 있는 시간을 구한다.

 

 

 

 

제약사항

 

사람은 10억명 이하, 심사대는 10만개 이하, 심사대 하나의 최대시간은 10억초이다.

 

하나의 케이스당 1초만에 풀어야 하니 딱 봐도 완전탐색으로는 풀지 못한다.

 

 

 

 

나의 풀이 과정

 

결국 구해야 하는 답은 걸리는 시간초이다.

 

몇 명이 어딜 어떻게 들어가던 다 들어갔을 때의 최소 시간만 구하면 된다.

 

결국 정답은 `0~걸리는 최악의 시간` 사이에 있을 것이라고 판단했고 이분탐색으로 풀이하였다.

 

 

가벼운 예시로 걸리는 최악의 시간을 먼저 찾아봤다.

 

심사대는 2개이고 친구는 6명이다.

 

 

사람들이 2번 심사대 누나가 너무 예뻐서 모두 거기로만 갔다고 쳐보자. 하지만 2번 누나는 1번에 비해 능력이 부족해 가장 오래걸리는 곳이었다.

 

이 시간초를 max 범위로 지정해도 되지만 좀 더 효율적인 방법이 있을 것이다.

 

 

일명 못생긴애들중 잘생긴애 찾기 전략 이다.

 

위의 이미지는 심사대들 중 가장 적은 시간이 걸리는 곳에 모든 심사자가 들어갔을 경우인데

 

단 한번이라도 분배해서 심사자들이 들어갔다면 이 시간초 보다는 반드시 빠를 것이다.

 

 

따라서 [최소시간인 심사대 X 심사자 수] 를 이분탐색의 MAX 범위로 선정하고 이분탐색을 진행했다.

 

MAX 범위 사이의 중간값(시간초)을 찾아가며 그 시간 초로 실제 각 심사대 시간초를 나눴을 때의 몫을 먼저 구한다.

 

그 몫은 하나의 심사대가 지정된 시간초(이분탐색하는 값)동안 커버할 수 있는 심사자 수라고 할 수 있다.

 

 

그걸 다 더해서 심사자 수보다 많으면 해당 지정된 시간초동안은 심사자들을 모두 커버할 수 있는 상태라고 할 수 있다.

 

이걸 이용해 이분탐색으로 최적화하여 최소 시간을 찾아나가면 된다.

 

 

 

이분탐색 과정을 간단하게 도식화 해보았다. 이 흐름을 코드로 옮기면 된다.

 

 

 

 

자바 풀이 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int[] inputArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[] simSaDae = new int[inputArr[0]];
        int friendsNum = inputArr[1];

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

        Arrays.sort(simSaDae);
        System.out.println(search(simSaDae, friendsNum));
    }

    private static long search(int[] simSaArray, int friendsNum) {
        long left = 0;
        long right = (long) simSaArray[0] * friendsNum;
        long result = Long.MAX_VALUE;
        while (left <= right) {
            long mid = (left + right) / 2;
            long sumOfFriends = Arrays.stream(simSaArray).mapToLong(value -> (mid / value)).sum();

            if (sumOfFriends >= friendsNum) {
                right = mid - 1;
                result = Math.min(result, mid);
                continue;
            }
            left = mid + 1;
        }
        return result;
    }
}

 

주의할 점은 심사대 하나가 시간 초가 10억 초 일 수 있기 때문에 이분탐색할 수치들을 long 타입으로 선정한 것이다.

 

최악중의 최선으로 선정했던 MAX 값이 충분히 21억을 넘어갈 수 있다.

 

이 풀이라면 심사대 수가 N(최대 10만) 일 때 최악의 테스트 케이스에서도 탐색에서 (OlogN) * N 만큼만 연산을 하여 1초안에 충분히 통과를 할 수 있다.