백준 2792 - 보석 상자

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

2792번: 보석 상자

 

* 문제 요약

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다.

원장 선생님은 모든 보석을 N명의 학생들에게 나누어주려고 한다.

이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 갯수이다.

원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어주는 경우를 생각해보자. RR, RR, BB, BB, BBB 로 보석을 나누어주면 질투심은 3이 되고, 이 값 보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 <= N <= 10^9, 1 <= M <= 300,000, M <= N)

다음 M개 줄에는 구간 [1, 10^9] 에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 갯수이다.

 

* 출력

첫째 줄에 질투심의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

start 를 1, end 를 각 색상의 보석들 중 가장 갯수가 많은 것으로 지정하여 범위를 설정해준다.

해당 범위의 중간값으로 현재 색깔의 보석을 나누었을 때 나머지가 0인 경우 몫만을 count 에 합산하고, 나머지가 0이 아닌 경우 count 에 중간값으로 현재 색깔의 보석을 나누어서 구한 몫을 합산하고 난 다음 1을 추가로 더해준다. 여기서 1을 추가로 더하는 이유는 나머지로 나온 값 만큼 남은 보석을 추가로 다른 아이에게 나누어주어야 하기 때문이다.

마지막으로 구한 count 값이 n보다 클 경우 mid 값으로 보석의 갯수를 나누었을 때 나오는 몫의 크기를 줄여야 하므로 start 를 mid + 1 로 초기화하여 mid 값이 커지는 방향으로 범위를 줄여주고, count 값이 n보다 작거나 같은 경우 result 를 mid 로 초기화한 다음 (나머지로 나온 보석 분배 갯수는 필연적으로 mid 보다 작을 수 밖에 없다.) end 를 mid - 1 로 초기화하여 mid 값이 작아지는 방향으로 범위를 줄여준다.

여기서 n보다 count 값이 작은 경우는 보석을 분배받지 못한 아이가 존재하는 경우에 해당된다.

 

마지막으로 result 를 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int[] jewelArray = null;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int color = Integer.parseInt(input[1]);
        jewelArray = new int[color];
        long max = Integer.MIN_VALUE;
        for (int i = 0; i < color; i++) {
            int colorCount = Integer.parseInt(br.readLine());
            jewelArray[i] = colorCount;
            max = Math.max(max, colorCount);
        }

        long start = 1;
        long end = max;
        long result = 0;
        while (start <= end) {
            long mid = (start + end) / 2;

            if (distribute(mid, n)) {
                result = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private boolean distribute(long mid, int n) {

        int count = 0;
        for (int i = 0; i < jewelArray.length; i++) {
            if (jewelArray[i] % mid == 0) {
                count += jewelArray[i] / mid;
            } else {
                count += (jewelArray[i] / mid) + 1;
            }
        }

        if (count > n) {
            return false;
        } else {
            return true;
        }
    }
}

 

초기에 1부터 각 색깔의 보석들 중 가장 갯수가 많은 보석의 갯수까지를 범위로 하여, 그 중간값으로 각 색깔의 보석의 갯수를 나눈 후에 구한 몫과 나머지를 합산한 값. 즉, 현재 중간값을 최대로 하여 아이들에게 나누어 주었을 때 보석을 분배받을 수 있는 아이들의 숫자가 유치원의 아이들 숫자보다 큰지, 작거나 같은지 여부에 따라 범위를 절반씩 줄여가며 정답을 찾았으므로 매개변수 탐색문제에 해당된다.