백준 3079번 입국심사 (JAVA)

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

3079번: 입국심사

 

저는 해당 문제를 이분 탐색을 통해서 해결하였습니다.

저는 이분탐색을 작은 값은 1 큰 값은 1,000,000,000 * 1,000,000,000로 하였습니다.

( N=1 , M = 1,000,000,000 , T1 = 1,000,000,000 이렇게 주어진다면 결과 값이 1,000,000,000 * 1,000,000,000 될 것이라 생각하였습니다.)

이분 탐색을 하면서 그 값안에 모든 사람이 검사를 받을 수 있는지 확인하였습니다.

저는 여기서 오류를 범하였습니다.

private static boolean checkInTime(int[] input, int n, int m,long time) {
    long peopleCnt = 0;
    for(int i = 0 ; i < n ; i++){
        peopleCnt += (time / input[i]);

    }
    if(peopleCnt >= m){
        return true;
    }
    return false;
}

저의 처음 해당 시간안에 m명의 사람을 검사할 수 있는지에 대한 함수입니다.

저는 long타입이기 떄문에 왠만하면 오버플로우가 나지 않을 것이라 생각하였습니다.

계산해보니 N = 100,000, M = 1,000,000,000 , T(all) = 1 라 했을 때 최대 값 1,000,000,000 * 1,000,000,000이 time으로 들어오면 peopleCnt가 1,000,000,000 * 1,000,000,000 * 100,000 = 10^24 가 되면서 오버플로우 발생할 여지가 있습니다.

그래서 저는 for문 안에 if문을 넣음으로써 오버플로우가 발생할 여지를 없애고 해결하였습니다.

 

package BOJ.binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_3079 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        int[] input = new int[n];
        for(int i = 0 ; i < n ; i++){
            input[i] = stoi.apply(br.readLine());
        }
        long answer = binarySearch(input,n,m);
        System.out.println(answer);
    }

    private static final long MIN_TIME = 1;
    private static final long MAX_TIME = 1_000_000_000L * 1_000_000_000L;
    private static long binarySearch(int[] input, int n, int m) {
        long result = MAX_TIME;
        long start = MIN_TIME;
        long end = MAX_TIME;
        while(start <= end){
            long mid = (start + end)/2;
//            System.out.println(mid);
            if(checkInTime(input,n,m,mid)){
                end = mid - 1;
                result = mid;
            }else{
                start = mid + 1;
            }
        }
        return result;
    }

    private static boolean checkInTime(int[] input, int n, int m,long time) {
        long peopleCnt = 0;
        for(int i = 0 ; i < n ; i++){
            peopleCnt += (time / input[i]);
            if(peopleCnt >= m){
                return true;
            }
        }
        return false;
    }
}