[BOJ] 3079 입국심사 (Java)

 

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

 

문제를 읽다보니 너어무 익숙했던,, 프로그래머스 문제와 동일했다

https://dev-zsunny.tistory.com/23

99클럽 코테 스터디 3일차 TIL 이분탐색(입국심사)

그래서 금방 풀어서 제출했지만 2%, 13%, 30% 계속  틀렸구,,, 또 자료형 문제였다!!!!!

분명 자료형 고려해줬다고 생각했는데, 심사 가능한 인원수를 계산하는 부분에서 주어진 M의 범위를 넘어가면 break; 를 한번 더 해주어야 했다..

(안그럼 total 값이 오버플로우 날 수도 있음)

알고리즘만 생각하다가 자료형 고려하는 거에 넘 신경을 못썼다,,, 

// 가능한 처리 인원
public static long calc(long mid){
    long total = 0;
    for(int i=0; i<n; i++){
        total += mid / arr[i];
        if(total > 1000000000) break;
    }
    return total;
}

 

<제출 코드>

package BOJ;

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

public class BOJ_3079 {

    static int n, m;
    static long ans = Long.MAX_VALUE;
    static int[] arr;

    // 가능한 처리 인원
    public static long calc(long mid){
        long total = 0;
        for(int i=0; i<n; i++){
            total += mid / arr[i];
            if(total > 1000000000) break;
        }
        return total;
    }

    public static void binarySearch(long s, long e){
        if(s > e) return;
        long mid = (s + e) / 2;
        long total = calc(mid);
        if(total >= m) {
            ans = Math.min(ans, mid);
            binarySearch(s, mid-1);
        }else {
            binarySearch(mid+1, e);
        }
    }

    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 int[n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        binarySearch(1, (long)m*arr[n-1]);
        System.out.println(ans);
    }
}