BOJ - 입국심사 3079번 (JAVA)

❓ 문제 - 백준 입국심사 3079번 - JAVA 풀이법

 

출처 

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

3079번: 입국심사

 

 

📝 문제해결법

1. 이 문제는 이진탐색(Binary Search)로 해결했다.

• 이진 탐색 -> 시간을 중심으로 탐색
• 해당 시간일 때 최대 몇 명의 사람을 입국 심사대에서 통과 시킬 수 있는가를 중점으로 이진탐색을 진행
• 만약 mid초일 때, m명 이상의 사람을 해당 시간에 입국 심사대에서 보낼 수 있음 -> 시간 탐색범위를 0 ~ mid-1
• 만약 mid초 일 때, m-1 이하의 사람을 해당 시간에 입국 심사대에서 보낼 수 있음 -> 시간 탐색 범위를 mid+1 ~right
• 처음 left는 0으로 설정, right는 각 입국심사대에서 걸리는 시간의 최대값(Tk) * 심사 받으려는 사람의 수(M)

2. 느낀점

• 일단... 탐색의 중심을 뭘로 잡느냐가 이 문제의 핵심인듯...
• 그리고 주어진 데이터의 범위가 말도 안되고 최적 조건을 찾는다 ? 그럼 바로 이진탐색을 떠올려보기..
• 이진탐색시 데이터 범위가 엄청 크므로 데이터 타입의 범위를 조심해서 변수타입을 지정하기...!

 

💻 소스코드

// BOJ - 입국심사(3079번)
// BinarySearch
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class BinarySearch_BOJ_3079 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N과 M 그리고 각 입국 심사대에서 걸리는 시간을 arr 배열에 데이터를 입력받음
        String[] data = br.readLine().split(" ");
        int n = Integer.parseInt(data[0]);
        int m = Integer.parseInt(data[1]);
        int[] arr = new int[n];
        // 그리고 가장 입국 심사대에서 오래 걸리는 시간을 max_value 로 구함
        int max_value = 0;
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
            max_value = Math.max(max_value, arr[i]);
        }
      
        long left = 0L;
        long right = (max_value) * 1000000000L;

        long ans = 0L;
        while (left<= right){
            long mid = (left+right) / 2;
            // mid초 일 때 각 입국 심사대에서 보낼 수 있는 수를 카운트 해줌
            long cnt = 0;
            for(int i=0;i<n;i++){
                cnt += (mid / arr[i]);

            }
            // 비교 후 탐색 범위 변경
            if(cnt >= m){
                ans = mid;
                right = mid-1;
            }  else if (cnt < m){
                left = mid +1;

            }
        }

        System.out.println(ans);

    }
}