📙[Algo] 24.02.02 알고리즘

알고리즘 문제) BOJ 2792. 보석 상자

2792번: 보석 상자

문제 요약

• 보석은 각각 M가지 서로 다른 색상 중 한 색상
• 모든 보석을 N명의 학들에게 나눠주려고 함
  • 못 받는 학생도 있지만, 항상 같은 색상의 보석만 가져갈 것
• 질투심 : 가장 많은 보석을 가져간 학생의 보석 개수
• 질투심이 최소가 되게 나눠 줄 것
• 보석 정보, 학생 수가 주어졌을 때 질투심이 최소가 되게 나눠주는 법?

시간 제한

• 1초

입력

• 아이들의 수 N, 색상의 수 M
  • 1≤N≤10억
  • 1≤M≤30만
  • M≤N
• M개의 줄에 구간[1,10억]에 포함되는 양의 정수가 하나씩 주어짐

출력

• 질투심 최솟값 출력

접근법

1. 완전탐색으로 생각하기
   학생 수 7명, 색상 수 5개
   각 색상별로 7, 1, 7, 4, 4 개 보석 존재
   보석은 모두 나눠줘야하며, 최대 7명한테 나눠줄 수 있다. 또한 한 사람에게는 같은 색상만 나눠줘야 한다.
   최대로 나눠줄 학생 수 한명을 지정한다. 그리고 최댓값부터 하나씩 감소해가면서 해당 학생에게 배분했을 때 남은 보석들을 완전히 나눠줄 수 있는 지 체크한다.
2. 최적화 하기
   현재 보석 중 최대 개수가 7개이므로, 7개를 기준으로 절반 나눈 3을 최대로 지정하게 된다면 남은 보석은 4 1 7 4 4가 되고, 남은 학생 수는 6명이 된다. 또한 최대 개수를 3개로 지정했으므로 3이하의 보석으로 나눴을 때 6명 내로 나눠지는 지 체크한다. 즉 남은 보석 수를 돌아가며 3으로 나눈 몫을 더해주고 나머지가 있다면 추가로 1만큼 더해준다.. 그때 만약 아직 남은 보석수가 있다면 3보다 더 큰 값으로 최대값을 지정해줘야 한다는 뜻! 만약 충분히 나눌 수 있다면 3보다 작은 값으로 한 번 더 탐색을 한다. 그때마다 최솟값을 갱신!
   
   접근 방식은 스스로 생각했는데, 남은 개수 생각하는 부분은 다른 사람 접근법 살짝 참고함!

코드

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


public class Main {
    static int[] jewels;
    static int N, M, max = Integer.MIN_VALUE;
    static long sum;
    static int answer = Integer.MAX_VALUE;

    static void binarySearch(int s, int e) {
        int mid;
        long total;
        int students;
        while (s <= e) {
            mid = (s + e) / 2;


            total = sum;
            students = N;
            for (int i = 0; i < M; i++) {
                if (students > 0) {
                    total = total - ((jewels[i] / mid) * mid + jewels[i] % mid);
                    students -= jewels[i] / mid;
                    if (jewels[i] % mid > 0) {
                        students--;
                    }
                } else break;
            }

            if (total <= 0 && students >= 0) {
                answer = Math.min(answer, mid);
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
    }




    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        jewels = new int[M];
        for (int i = 0; i < M; i++) {
            jewels[i] = Integer.parseInt(br.readLine());
            sum += jewels[i];
            max = Math.max(max, jewels[i]);
        }

        binarySearch(1, max);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}