[240319] 알고리즘 리부트 33일차 - 백준 2792 자바

구하고자 하는 바를 기준으로 로직을 생각하니 금방 구현할 수 있었다. 여기서 구하고자 하는 건 질투심 즉, 가장 사탕을 많은 아이의 사탕 갯수이다. 사탕 갯수 배열을 두번만 돌아도 백억을 넘기 때문에 시간 초과가 발생할 것이고 이분 탐색을 활용해서 풀이한다.

left는 [1, 10^9] 구간 중 1이 가장 적은 사탕의 수가 되고 가장 사탕의 수가 많은 종류를 한 아이가 다 받는 경우 즉, 10^9가 right이다. 이를 테스트케이스에 적용하면 색상별 사탕의 수를 입력 받고 해당 배열을 정렬하면 첫번째 원소에는 최소 질투심이 될 수 있는 수, 마지막 원소에는 최대 질투심이 될 수 있는 수가 담겨있다.

이를 통해 이분 탐색을 진행하고 중간 값인 m 값이 질투심이라고 가정했을 때, 반복문을 돌면서 해당 질투심의 갯수로 몇명의 아이가 사탕을 받을지 cnt로 구한다. 만약 cnt가 학생 수보다 많을 때에는 문제에서 지시함 '모든 보석을 나누어 준다'라는 부분을 충족하지 못하기 때문에 l을 늘린다. 반대로 cnt가 학생 수와 같거나 그보다 적을 때는 더 작은 질투심을 가진 분배가 이루어질 수 있기 때문에 ans로 갱신하면서 r을 줄여준다. 

사탕 배열에 대해 반복문을 돌면서 학생 수를 구할 때는 사탕의 수(=질투심)에 나머지 연산을 수행해서 0인 경우는 몫을 더해주고 0이 아닌 경우에는 몫+1 값을 해준다. 두 사탕 색상을 한 아이에게 줄 수 없기 때문에 적게 배분되더라도 그 사탕 색상에서 분배하고 끝내버리는 것이다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int student = sc.nextInt();
        int color = sc.nextInt();

        int[] jewels = new int[color];

        for (int i = 0; i < color; i++) {
            jewels[i] = sc.nextInt();
        }

        Arrays.sort(jewels);
        //System.out.println(Arrays.toString(jewels));

        // 질투심 즉, 한 아이가 가질 수 있는 최대 사탕의 수를 구하는 것
        int l = 1;
        int r = jewels[color - 1]; // 가장 많은 사탕 갯수가 있는 종류를 한 아이가 다 가지면 최대값

        int ans = -1;

        while (l <= r) {
            int m = (l + r) / 2;

            int tmp = getCnt(m, jewels);

            if (tmp <= student) {
                ans = m;
                r = m - 1;
                //System.out.println("r 줄임: " + r);
            } else {
                l = m + 1;
                //System.out.println("l 늘림: " + l);
            }
        }
        System.out.println(ans);
    }

    private static int getCnt(int m, int[] jewels) {
        //System.out.println("현재 m: " + m);
        int cnt = 0;
        for (int i = 0; i < jewels.length; i++) {
            if (jewels[i] % m != 0) cnt += (jewels[i] / m) + 1;
            else cnt += jewels[i] / m;
            //System.out.println("현재 cnt: " + cnt);
        }

        return cnt;
    }
}