[JAVA46] 3079. 입국심사

3079. 입국심사 (G5)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	29418	5802	3796	23.678 %

 

문제

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

출력

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

.

---

summary

심사를 마치는데 걸리는 시간의 최솟값

 

• 각 심사대마다 심사시간이 있음
• 비는 자리에 바로 안들어가도 됨

 

strategy

이분탐색 (시간을 기준)

 

• 제일 작은 시간과 제일 큰 시간 중간 값을 구함 (mid)
• 중간 값 시간으로 심사할 수 있는 인원 구함 (sumCnt)
• 인원수보다 많으면 제일 큰 값을 줄임 (end = mid - 1)
• 인원수보다 적으면 제일 작은 값을 늘림 (start = mid + 1)

 

note

• 1 ≤ N(심사대 개수) ≤ 100,000
• 1 ≤ M(사람수) ≤ 1,000,000,000
• 1 ≤ Tk(걸리는시간) ≤ 10^9

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

class Main {

    static int N, M;
    static int[] gates;
    static long answer = 0;
    
    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());

        gates = new int[N];
        for(int n = 0; n < N; n++) {
            gates[n] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(gates); 

        // 초를 기준으로 이분 탐색 (상한)
        answer = upperBound();

        System.out.println(answer);
    }

    private static long upperBound() {
        long start = gates[0]; 
        long end = (long) M * gates[0];

        while(start <= end) {
            long mid = (start + end) / 2;

            long sumCnt = 0;
            for(int gate : gates) {
                sumCnt += (mid / gate);
            }

            if(sumCnt >= M) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }
}
import java.util.*;
import java.io.*;

class Main {

    static int N, M;
    static int[] gates;
    static long answer = 0;
    
    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());

        gates = new int[N];
        for(int n = 0; n < N; n++) {
            gates[n] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(gates); 

        // 초를 기준으로 이분 탐색 (상한)
        answer = upperBound();

        System.out.println(answer);
    }

    private static long upperBound() {
        long start = gates[0]; 
        long end = (long) M * gates[0];

        while(start <= end) {
            long mid = (start + end) / 2;

            long sumCnt = 0;
            for(int gate : gates) {
                sumCnt += (mid / gate);
            }

            if(sumCnt >= M) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }
}

문제	결과	메모리	시간	언어코드	길이
3079	맞았습니다!!	28616 KB	408 ms	Java 11 / 수정	1150 B

 

memo

변수에 long 값만 주고 계산 변수를 신경안씀 ... (범위 체크 문제인줄 알고 계속 삽질함)

// long end = M * gates[0]; (X)

long end = (long) M * gates[0];