[백준] 13072 이상한 술집 - 파라매트릭 서치(ParamatricSearch) JAVA

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

코드설명

파라매트릭 서치(ParamatricSearch) 를 활용합니다.

 

항상 파라매트릭 서치에서는 시작점과 끝점의 설정과 자료형 설정이 중요합니다.

우선 시작점의 경우, 막걸리의 음료양은 반드시 1 부터 시작합니다. 끝양은 주전자에 든 막걸리 값들 중 최대값으로 설정합니다.(이때, 2^31 - 1 로 하면되는것 아닌가? 라는 생각이 듭니다. 하지만, 제가 구현한 Optimize 코드에서는 작동하지 않습니다. 이진탐색을 어떻게 구현했느냐에 따라 달라질 수 있습니다. 사실 이 부분은 저도 명확한 구별이 어려워, 명확히 설명이 불가한 부분입니다..)

코드

정답코드입니다. 유의할점은, 막걸리의 용량은 2^31 -1 보다 작거나 같은 자연수 또는 0이다.  라는 부분입니다.

이 과정에서 mid = (left + right) / 2 일떄, left + right 가 더 해지면서 int형 범위를 벗어납니다.

그러므로 long 형을 선언합니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K;
	static int answer = 0;
	static int[] 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());
		K = Integer.parseInt(st.nextToken());
		int max = 0;
		arr = new int[N];
		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		System.out.println(optimize(1, max));
	}
	
	static boolean isDivideable(long value) {
		
		int cnt = 0;
		for(int i=0;i<N;i++) {
			cnt += arr[i] / value;
		}
		return cnt >= K; 
	}
	static long optimize(int lo, int hi) {
		long left = lo - 1; 
		long right = hi + 1;

		while(left + 1 < right) {
			long mid = (left + right) / 2;
			if(isDivideable(mid)) {
				left = mid;
			}else {
				right = mid;
			}
		}
		return right - 1;
	}
	
}

 

만약, 탐색 횟수를 강제하고 싶을경우( 이 경우는 소수점의 정밀도 관련해서 처리할 떄 사용하는 방식입니다. )

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K;
	static int answer = 0;
	static int[] 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());
		K = Integer.parseInt(st.nextToken());
		int max = 0;
		arr = new int[N];
		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		System.out.println(optimize(1, max));
	}
	
	static boolean isDivideable(long value) {
		
		int cnt = 0;
		for(int i=0;i<N;i++) {
			cnt += arr[i] / value;
		}
		return cnt >= K; 
	}
	
	static long optimize(int lo, int hi) {
		long left = lo - 1; 
		long right = hi + 1;

		for(int it = 0; it < 100; it++) {
			long mid = (left + right) / 2;
			if(isDivideable(mid)) {
				left = mid;
			}else {
				right = mid;
			}
		}
		return right - 1;
	}
	
}