[백준] 3079 입국심사 - 파라매트릭 서치(Paramatric Search) JAVA

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

3079번: 입국심사

코드설명

파라매트릭 서치 문제입니다.

 

문제를 어떻게 접근해야할지 상당히 어려운 문제였습니다.

 

1. 이 문제에서 가장 중요했던 점은, 

"시간 / 각 심사대의 심사시간 = 심사받을 수 있는 최대 인원 수" 라는것을 알아내야합니다.

//middle초 내 / 각 심사대의 심사 시간 = 심사받을 수 있는 최대 인원 수 
for(int i=0;i<N;i++) {
    value += ( middle / arr[i] );
    if(value >= M) break;
}

문제에서 "만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다." 이런 조건 때문에 이것이 최소 시간이 맞을까 라는 의문이 생기는데 해당 내용을 빨리 파악한다면 손쉽게 풀 수 있는 문제였습니다.

 

2. 문제 조건에 Tk 가 1 <= Tk <= 10^9 이므로

아래 코드처럼 비교시간이 M보다 크다면 종료시켜야만 OverFlow가 발생하지 않습니다.

( Tk가 10^9 인데, N 또한 100,000 이라면, 각 인원을 구하는 과정에서 Overflow가 발생합니다. )

    if(value >= M) break;

3. 이 문제의 매개변수는 Value, (총 몇명이 심사받을 수 있는가) 이므로 해당 내용을 가지고서 반복문을 진행하며 가장 최소의 시간을 구할 수 있습니다.

코드

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

public class Main {
	public static int N, M, K = 0;
	public static long[] arr; 
    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 long[N];
    	
    	long end = 0;
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Long.parseLong(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
    	
    	paramatricSearch(0, end);
    }
    
    public static void paramatricSearch(long start, long end) {
    	long left = 0; //최소시간.
    	long right = end * M; //최악의 시간.
    	
    	while(left <= right) {
    		long middle = (left + right) / 2; //시간을 미리 정해둡니다.
    		
    		long sum = 0;
    		for(int i=0;i<N;i++) {
    			sum += (middle / arr[i]); //주어진 시간에서 각 심사대가 심사할 수 있는 사람 명.
    			if(sum > M) break; //반드시 sum이 OverFlow 될수 있으니 중간에 중단시켜주어야합니다.
    		}

    		//만약 주어진 시간에서 심사할 수 있는 인원이 상근이와 친구들보다 더 많다면, 
    		//최대시간을 줄여야 심사할 수 있는 인원을 줄일 수 있습니다.
    		if(sum >= M) {
    			right = middle - 1;
    		}
    		//만약 인원보다 작다면, 시간을 늘려줘야합니다.
    		else if(sum < M) {
    			left = middle + 1;
    		}
    		
    	}
    	System.out.println(right + 1);
    }
    
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static long start = 0, end = 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());
    	arr = new int[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end,  arr[i]);
    	}
    	
    	paramatricSearch();
    	
    }
    public static void paramatricSearch() {
    	start = 0;
    	end *= M;
    	
    	while(start <= end) {
    		long middle = (start + end ) / 2;
    		
    		long value = 0;
    		//middle초 내 / 각 심사대의 심사 시간 = 심사받을 수 있는 최대 인원 수 
    		for(int i=0;i<N;i++) {
    			value += ( middle / arr[i] );
    			if(value >= M) break;
    		}
    		
    		if( value >= M ) {
    			end = middle - 1;
    		}else {
    			start = middle + 1;
    		}
    		
    	}
    	System.out.println(end + 1);
    	
    }
    
}