Q 2792 보석 상자

💡 문제 요약 및 분석

보석 상자의 보석들을 N명의 학생들에게 나눠주는 상황이다. 학생은 같은 색깔의 보석만 가져갈 수 있고, 다른 학생이 자기보다 더 많이 가져가면 질투한다. 내가 2개, 다른 아이가 3개를 가져갔을 때의 질투심을 수치화 하면 3이 된다. 이 질투심이 최소가 되도록 보석을 나눠주자.

💡 알고리즘 설계

🔥 답지를 보고 풀었다. ‘질투심이 최소가 된다 == 학생들 각자 비슷한 개수의 보석을 가진다’를 전제로 두고 ‘가장 적게 받는 경우 1개 + 가장 많이 받는 경우 M.max / 2’ 를 중간값으로 두고 보석을 나누는 경우의 수를 계산하자.

  1. 입력

    • 표준입력으로 int N, int M 저장한다.
    • 표준입력 받는 보석의 개수를 int[M] 배열에 저장한다.

  2. 연산

    • left = 1, right = max
    • 중간값(mid) 를 계산한다. mid = (left + right) / 2
    • 주어진 보석의 개수를 mid 로 나눈다. 딱 맞게 나누어 떨어지면 그 몫을 보석을 받은 인원 수에 추가하고, 맞아 떨어지지 않으면 몫 + 1 하여 추가한다.
    • 최종적으로 모든 보석을 mid 개 나누어주었을 때의 인원 수 > N 이라면 보석을 나눠주는 개수(mid)가 더 커야 한다는 의미로, left 포인터를 mid + 1 로 옮긴 후 다시 계산한다. (왼쪽 절반을 버림)
    • 인원 수 < N or 인원 수 == N 경우에는 해당 mid 를 결과(result)로 저장해두고 right 포인터를 mid - 1 로 옮긴 후 다시 계산한다. (오른쪽 절반을 버림)

  3. 출력

    • result 변수를 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int M = read();
        int[] jewels = new int[M];
        int max = 0;
        for (int i = 0; i < M; i++) {
            int input = read();
            max = Math.max(max, input);
            jewels[i] = input;
        }

        int left = 1;
        int right = max;
        int result = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            int count = 0;
            for (int i = 0; i < M; i++) {
                if (jewels[i] % mid == 0) {
                    count += jewels[i] / mid;
                } else {
                    count += jewels[i] / mid + 1;
                }
            }

            if (count > N) {
                left = mid + 1;
            } else {
                right = mid - 1;
                result = mid;
            }
        }
        System.out.println(result);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(m * log m)O(m)

💡 느낀점 및 기억할 정보

이분 탐색

정렬된 데이터에서 찾고자 하는 값을 중간값과 비교해 절반씩 버리면서 탐색하는 알고리즘이다. 전제 조건은 데이터가 정렬되어 있어야 한다는 점이다. 시간 복잡도는 O(log N) 이다. 동작 방식은 1. 중간값과 목표값을 비교한다. 2. 목표값이 중간값보다 크면 왼쪽을 버리고, 작으면 오른쪽을 버리고 새로운 중간값을 구한다. 3. 이 과정을 중간값 == 목표값이 될 때까지 진행한다. 아래 예시를 통해 이해해보자.

int arr = [1, 3, 5, 7, 9, 11];
int target = 7; // 찾고 싶은 값 = 7

int left = 0;
int right = arr.length - 1;

while (left <= right) {
    int mid = (left + right) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        // 목표값이 중간값보다 작다. 오른쪽 부분을 버리자.
        right = mid - 1;
    } else if (arr[mid] < target) {
        // 목표값이 중간값보다 크다. 왼쪽 부분을 버리자.
        left = mid + 1;
    }
}