[백준] Gold V. 입국 심사

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

27614

5272

3461

23.686%

문제

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 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)

출력

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

 

문제 유형

• 이분 탐색

풀이

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

public class Main {
    static int n, m; // n: 입국 심사대 개수, m: 사람 수
    static long[] arr;
    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());

        arr = new long[n];

        long lo = 1;
        long hi = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if (arr[i] > hi) hi = arr[i];
        }

        hi = (long) (hi * m);


        while(lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long result = 0;
            for(int i = 0; i < arr.length; i++) {
                result += (mid / arr[i]); // 30 / 7 + 30 / 10 = 7
                if (result >= m) break;
            }

            if (result < m) {
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        System.out.println(lo);
    }
}

 

회고

 

처음에 이분탐색의 비교를 어떻게 해야할지 고민을 하다가 답을 참고했는데, arr안에 있는 숫자를 돌면서 mid 값을 나눔해주면 해당 시간이 수용할 수 있는 인원 수가 나온다.

 

그래서 처음에 mid값을 30으로 설정하고, arr 숫자가 7, 10이라면 최대 수용할 수 있는 인원 수는 7명이 된다.

 

이 때, 문제에서 주어진 6명보다 더 많이 받을 수 있다는 뜻은 시간을 더 줄여도 된다는 뜻이니 상한점을 낮춰서 mid값을 줄여주면 된다.

 

주의사항

정답은 맞았는데 계속 문제를 제출해도 32퍼센트에서 틀렸다고 떴다. 

 

result가 M을 초과할 때 break를 해주지 않으면 오버플로우가 나기 때문인데, 문제에서 N은 100,000, M은 1,000,000,000이고 arr의 값이 1이라면, (M / 2) * N을 할 때 값이 매우 커지기 때문에 break를 해줘서 오버플로우를 방지해줘야 한다.

 

정답률이 23프로인데 시초때문에 까다로워서 그런것같다