[백준] 2792 보석 상자 - 파라매트릭 서치(Paramatric Search) JAVA

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

2792번: 보석 상자

코드설명

파라매트릭 서치 문제입니다. 해당 알고리즘의 시간복잡도는 O(log N) 입니다.

 

우선, 이 문제가 파라매트릭 서치라는 점은 어느정도 예측할 수 있었습니다.

하지만, 파라매트릭 서치의 최적화 문제(optimize)를 작성하는 부분에 아이디어가 생기지 않아, 코딩을 하지 못했습니다.

이유는, 문제에서 질투심이 최소 3개일떄의 예시를 보면 RR RR RRR BB BB 이런식으로 나누는데, 실제적으로 코딩을 할때는 이러한 예시대로 코딩하는 것으로는 답을 찾지 못하고, RRR RRR R BBB B 이렇게 이 3개로 나눌 수 있느냐 없느냐로 최적화 문제(optimize)를 해결해야하는데, 이 최적화 문제를 작성하지 못하니 결정 문제(deicison problem)을 더이상 손대지 못합니다. 즉, 문제의 예제와 다르게 접근해야 풀 수 있다는 점에서 어려웠습니다.

 

문제를 더 설명해보면, 질투심 = 모든 학생들 중 보석을 가장 많이 가져간 학생의 보석 갯수입니다.

즉, 한명한테 보석을 모두 나눠주면 질투심이 높아집니다. 각 인원에게 보석의 개수를 최대한 적게 나누어주면서 질투심을 최소화 시켜야합니다.

이 문제에서 질투심이 최소가 되게 보석을 나누어주기 위해서는 각 인원에게 나누어주는 보석의 개수를 최대한 감소시켜야합니다. ( 그래야지 서로간의 보석 차이가 적습니다. )

 

관련 로직은,

1. 파라매트릭 서치에서 매개변수는 "나눠줄 보석의 수" 입니다.
2. 매개변수로 설정된 값으로 총 몇명의 사람에게 나눠줄 수 있는지 계산합니다.

3. 계산하였을때의 사람 인원수가 나누어줄 사람인 N보다 크다면, 나눠주는 보석의 개수를 증가시켜서 사람 인원수를 줄여줍니다. 

4. 계산하였을때의 사람 인원수가 나누어줄 사람인 N보다 작거나 같다면, 나눠주는 보석의 개수를 감소시켜서 사람 인원수를 증가시킵니다. 여기서 N보다 작거나 같은경우까지 확인하는 이유는, 우리가 구하는 것은 질투심의 최소값이기에 나눠주는 보석의 양을 최대한 감소시켜야합니다.  예시로 들어보면, 10명이 있을때 3개씪 나눠줄경우 3 3 3 1 이며, 2개씩 나눠줄경우 2 2 2 2 2 로 질투심이 적습니다. 물론 같은 인원인 경우가 아니지만, 계속해서 탐색을 진행할경우 같은 인원이면서 나눠주는 개수가 같은 경우가 있을 것 입니다.

 

코드

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 answer = 0;
	public static int 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[M];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
    	
    	paramatricSearch();
    }
    
    //파라매트릭 서치에서 매개변수는 "나눠줄 보석의 수", 
    //매개변수로 나눠주었을때 총 몇명의 사람에게 나눠줄 수 있는지 계산하고, 계산하였을때의 사람 인원수가 N보다 크다면, 나눠주는 보석의 개수를 증가시켜서 사람 인원수를 줄여줍니다.
    //이 문제에서 질투심이 최소가 되게 보석을 나누어주기 위해서는 보석의 개수를 최대한 감소시켜야합니다. ( 그래야지 서로간의 보석 차이가 적습니다. )
 
    // 한명한테 보석을 모두 나눠주면 질투심이 높아집니다.
    // 최대한 많은 사람에게 동일하게 보석을 나눠줘야합니다.
    // 질투심 = 모든 학생들 중 보석을 가장 많이 가져간 학생의 보석 갯수입니다.   
    public static void paramatricSearch() {
    	start = 1; // 보석의 최소 개수는 1로 설정
    	end = end; // 색깔 상관없이 보석 중의가장 많은 색깔의 최대 개수 
    	
    	while(start <= end) {
    		int middle = ( start + end ) / 2; // 보석을 몇개씩 나눠줄 것인가.
    		
    		int peopleCnt = 0;
    		for(int i=0;i<M;i++) {
    			peopleCnt += arr[i] / middle; // ( k번쨰 보석의 개수) / ( 한 사람당 나눠줄 보석의 개수 ) = ( 가져가는 사람의 인원 )
    			if(arr[i] % middle > 0) //만약 나누어떨어지지 않으면, 보석이 남을때는 1 사람에게 남은 보석을 나눠줍니다. (한 사람은 1가지의 보석박에 못가지므로 이렇게 처리합니다.)
    				peopleCnt += 1; //보석을 나눠줍니다.
    		}
    		
    		if(peopleCnt > N) { // (나누어준 사람)이 N보다 크다면, 나눠줄 보석의 개수를 크게해줘서 나누어준 사람을 줄입니다.
    			start = middle + 1;
    		}else { // 만약 인원수가 같거나 작다면, ( 한 사람당 나눠줄 보석의 개수 ) 를 최대한 작게해주어야 질투심이 최소값이 되므로 아래와 같이 처리합니다.
    			end = middle - 1;
    		}
    	}
    	
    	System.out.println(start);
    }

}

 

정답코드2입니다.

가장 중요한점은, 아래의 코드겠지요.

    if(decision(mid) == true) {
        right = mid;
    }else {
        left = mid;
    }

사탕의 개수를 people <= N이 될떄까지 파라매트릭 서치가 반복되면서 결국에는 people <= N이 되는 지점(가장 N과 가까워지는 지점까지) 계속 반복할 것 입니다.

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, A, B, X, L, R, C, n, k, m, l, K, D, T, d, c;
	static int answer = 0;
	static int[] arr = new int[300001];
	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());
		
		int hi = 0;
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(optimize(1, (int) 1e9));
	}
	
	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) {
				right = mid;
			}else {
				left = mid;
			}
		}
		return right;
	}
	
	static boolean decision(int value) { //각자 value개의 보석개씩 나눠준다고할때, value개로도 N명 이하의 사람들에게 나눠줄 수 있냐? (N명이하인 이유는 보석을 나눠주는 것은 어떻게든 조절이 가능하기 때문임)
		long people = 0;
		for(int i=0; i<M; i++) {
			people += arr[i] / value;
			if(arr[i] % value > 0) {
				people += 1;
			}
		}
		return people <= N;
	}
	
}