[백준] 16401 과자 나눠주기 - 파라매트릭 서치(Paramatric Search) JAVA

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

16401번: 과자 나눠주기

코드설명

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

 

시간복잡도

일반적인 for문으로 계산할경우

- 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000) 이기에

O( N N)의 최악의 경우가 발생합니다. ( 과자의 수를 M만큼 확인하는것이 아닌 모든 과자의 수 N을 N번 확인해야합니다. )

 

파라매트릭 서치를 활용할경우 시간복잡도인 O(N log N) 으로 해결이 가능합니다.

 

문제에서 헷갈렸던점은, 

1. 단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

해당 조건을 어떻게 처리해야할지 고민을 했지만, 파라매트릭 서치를 진행하다보면 계속해서 값을 나눠줄 수 없는경우 middle값이 0으로 수렴하게 됩니다. 그렇게 되면, start값보다 end값이 줄어들며 자동으로 end 값이 -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 int start = 1000000000, end = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	N = Integer.parseInt(st.nextToken());

    	st = new StringTokenizer(br.readLine());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
 
    	paramatricSearch();
    	
    }
    
    public static void paramatricSearch() {
    	start = 1; //divide by zero error를 피하기 위함. 처음에 min으로 했었는데 1 로 수정
    	end = end;
    	
    	while(start <= end) {
    		int middle = ( start + end ) / 2; //적정 과자길이
    		
    		int cnt = 0;
    		for(int i=0;i<N;i++) { //해당 과자길이로 모든 조카들에게 같이 나눠줄 수 있는지 확인합니다.
    			//middle값인 5만큼 나눠준다고 생각하자.
    			//현재 과자길이보다 middle값이 작다면, 나눠줄수 있고, 해당과자를 몇번 나눠줄 수 있는지 확인한다.
    			if(arr[i] - middle >= 0) {
    				cnt += arr[i] / middle;
    			}
    		}
    		
    		
    		if(cnt >= M) { //조카의 수보다 더 나눠준 값이 같거나 많다면, 나눠주는 값을 늘려줘야합니다. 처음에는 > 으로 진행했지만, 이렇게 할경우 최대값이 아닌 조건에 해당하는경우에만 나옵니다. 문제의 조건에 최대값을 찾기 위해 >= M으로 처리합니다.
    			start = middle + 1;
    		}else {
    			end = middle - 1;
    		}
//    		System.out.println("start "+start+" end "+end+" cnt:"+cnt+" middle:"+middle);
    	}
    	
    	System.out.println(end); //적절한 값이 없을경우 계속해서 middle이 작아지면서 middle이 0으로 수렴하게 되므로 불가능한경우 -1 이 출력됩니다.
    }
    
    
	

}

 

정답코드2 입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, B, a, b;
	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());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		int max = 0;
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, arr[i]);
		}
		answer = optimize(1, max);
		if(answer <= 0) System.out.println(0);
		else System.out.println(answer);
		
	}
	
	static boolean decision(int length) {
		int cnt = 0;
		for(int i=0; i<N; i++) {
			cnt += arr[i] / length; 
		}
		return cnt >= M;
	}
	static int optimize(int lo, int hi) {
		int left = lo - 1; //최저 막대기 길이.
		int right = hi + 1; //최고 막대기 길이.
		while(left + 1 < right) {
			int mid = (left + right ) / 2;
			if(decision(mid) == true) {
				left = mid;
			}else {
				right = mid;
			}
		}
		return right - 1;
	}

}