백준 입국심사(3079)

 

오늘은 이진탐색 문제를 하나 풀어보았다.

 

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

3079번: 입국심사

 

입국심사를 최소 시간을 돌 수 있는 케이스를 찾아보기 위해서

 

시간을 이분탐색하며 해당 시간에 모두 심사를 마칠수 있는지 체크하는 방식으로 진행했다.

 

알고리즘은 맞는거 같은데 틀리길래 확인해보니 나는 최대로 오래걸리는 입국심사위원 * 대상자가 최대 시간이라 생각했는데 이러면 overflow가 나오는거 같다 그리하여 최소입국 심사위원으로 변경하니 해결되었다.

 

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

/**
 * https://www.acmicpc.net/problem/3079
 */
public class Main {

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

    public static void binarySearch() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        long[] gate = new long[N];
        long min = Integer.MAX_VALUE;

        for (int i=0 ; i < N; i++) {
            gate[i] = Integer.parseInt(br.readLine());
            min = Math.min(min, gate[i]);
        }

        long time = binarySearch(0, min * M, gate, M);

        System.out.println(time);
    }


    public static long binarySearch(long start, long end, long[] gate, int count) {
        if (start > end) {
            return start;
        }

        long mid = (start + end) / 2; // 중간 시간
        long sum = 0; // 통과 누적 수
        for (long j : gate) sum += mid / j;

        if (sum > count) { // 시간이 널널
            return binarySearch(start, mid - 1, gate, count);
        } else if (sum < count) { // 시간 부족
            return binarySearch(mid + 1, end, gate, count);
        } else {
            return binarySearch(start, mid - 1, gate, count);
        }
    }

}

 

결과