BaekJoon 3079 - 입국심사

처음 봤을 때 어떻게 풀어야 할지 굉장히 막막했던 문제다,,,

아직 신생아 뺨치는 알린이인 나에겐 굉장히 고통스러웠던 문제 😢

몇 시간 동안 풀다 구글님께 도움을 받아 문제를 풀 수 있었다.

 

일단 문제를 살펴보고 솔루션을 생각하자 〰️ 

 

 

 

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

 

출력

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다. 

 

 

예제 입력 1 

2 6
7
10

 

예제 출력 1

28

 

예제 입력 2

7 10
3
8
3
6
9
2
4

 

예제 출력 2

8

 

 

---

 

문제는 위와 같다. 사실, 생각했던 개념보다 솔루션은 굉장히 단순했다. 

이진탐색을 통해 답을 알아낼 수 있었는데, 처음엔 이진 탐색으로 도대체 어떻게! 알아냈는지 이해도 안갔다 〰️ 😎

이제 문제를 보는데 두 번째 예제를 그림으로 살펴보도록 하자 〰️ 

 

N = 7, M = 10이고, 입국 심사대 각각의 소요시간은 3, 8, 3, 6, 9, 2, 4 초씩 걸린다.

이 때, M(=10)명이 입국 심사를 가장 빨리 끝내는 시간은 얼마일까? 

 

 

 

다시 존댓말 모드,,,

위의 그림과 같이 8초가 걸릴 수 있습니다.

사실, 다른 조합으로 똑같이 8초가 걸릴 수 있는데 대충 하나 골라서 그려봤습니다 ~.~

 

정말 많은 시도를 했보았는데, 결과적으로 '이진 탐색'으로 풀어보도록 하겠습니다.

일단 코드를 보면 아래와 같습니다.

 

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

public class BaekJoon3079 {
    static long n, m;
    static long[] time;
    static long max =0;

    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Long.parseLong(st.nextToken());
        m = Long.parseLong(st.nextToken());
        time = new long[(int) n];


        for (int i = 0; i < n; i++) {
            time[i] = Long.parseLong(br.readLine());
            max = time[i] > max ? time[i] : max;
        }

        binarySearch();
    }

    private static void binarySearch() {
        long left = 1;
        long right = max*m;
        long result = right;
        long mid;

        while (left <= right) {
            mid = (left + right) / 2;

            if (isPossible(mid)) {
                result = Math.min(result, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(result);
    }

    private static boolean isPossible(long t) {
        long temp = 0;
        for (int i = 0; i < n; i++) {
            temp += t / time[i];
        }
        return temp >= m;
    }
}

 

위를 보시면 BufferedReader 와 StringTokenizer를 사용해서 값을 받아왔는데, Scanner의 nextLong으로 받으셔도 상관없습니다 〰️ 

다만, 위와 같이 사용하면 메모리나 속도 측면에서 약 4배 정도 성능이 좋아집니다 ❗️ 

 

데이터를 각각 받아오고 Binary Search를 실행시켰습니다.

 

핵심은 isPossible 을 사용한 분류입니다.

isPossible은 각각의 압국 심사대에 몇 명의 인원을 통과시킬 수 있는지 파악합니다.

만약 t라는 초동안 상근이의 친구를 전부 통과시킬 수 있다면 True, 없다면 False를 반환합니다.

 

예를 들어 t가 7초 였을 때, 모든 입국심사대를 통과할 수 있는 최대 인원은 3, 8, 3, 6, 9, 2, 4 초의 순서대로 2, 0, 2, 1, 0, 3, 1 명이기 때문에 에 10명을 전부 못 통과시킵니다.

그럼 False를 반환하겠죠?

 

반면 8초나 그 이상이라면 최소 12명을 통과시킬 수 있기 때문에 True를 반환합니다.

8초나 그 이상의 초가 답이 될 가능성이 있다는 의미이죠!

 

 

그럼 이번 포스팅은 여기서 마치겠습니다 ❗️ 

알린이 화이팅ㅇ,,,ㅎㅎ