[백준] 2792번 보석상자 (JAVA)

문제

- 보석은 M가지로 서로 다른 색상 중 한 색상

- 모든 보석을 N명의 학생들에게 나누어 주려고 함

- 보석을 받지 못하는 학생이 있어도 됨

- 학생은 항상 같은 색상의 보석만 가져감

- 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투함

- 이런 질투심을 수치화하는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수

- 질투심이 최소가 되게 보석을 나누어 주려고 함 (질투심의 최솟값 출력)

 

해결방법

이분 탐색 문제를 많이 풀어보고 싶어서 선택했던 문제였기 때문에 바로 이전에 포스팅한 문제와 문제 풀이 방식은 거의 유사했다.

2023.02.26 - [Algorithm/Baekjoon] - [백준] 16401번 과자 나눠주기 (JAVA)

이분 탐색을 통해 보석을 나누어 가지는 방식으로 코드를 작성하였고, 보석의 개수가 현재 탐색하고 있는 개수로 딱 떨어지면 나누기를 통해 나누어 줄 수 있는 인원을 계산할 수 있지만, 딱 떨어지지 않으면 인원을 한 명 더 배치해야 한다. (모든 보석을 나누어 주어야 하기 때문에)

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] jewels = new int[M];
        long result = 0;

        for(int i = 0; i<M; i++) {
            jewels[i] = Integer.parseInt(br.readLine());
        }
		
        // 보석 개수 순으로 정렬
        Arrays.sort(jewels);
		
        // 이분 탐색
        long left = 1;
        long right = jewels[M-1];

        while(left <= right) {
            int count = 0;
            long mid = (left + right) / 2;
			
            // 이분 탐색을 통해 특정한 개수만큼 보석 나누어주기
            for(int i = M-1; i>=0; i--) {	
            	// 보석의 개수가 특정한 개수로 나누어 떨어질 때
                if(jewels[i] % mid == 0) count += jewels[i] / mid;
                // 보석의 개수가 특정한 개수로 나누어 떨어지지 않아 다른 1명에게 추가로 분배해야 할 때
                else count += jewels[i] / mid + 1;
            }
			
            // 계속해서 질투심을 최소화 하기
            if(count <= N){
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(result);
    }
}