boj2792 보석 상자_java

링크

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

문제

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

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

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

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

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

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

출력

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

나의 풀이

• 내가 가지고 있는 보석중 보석개수가 가장 많은 것을 right에 넣자.
  left와 right를 갱신하여 최대 mid개의 보석을 가지는 경우를 만들수 있는지 while문을 돌면서 체크할 수 있도록 로직을 짰다.
• 7개의 보석을 mid인 4개씩나눠준다고하면, 2명의 인원이 이 보석을 받을것이고, 4개의 보석을 mid인 4개씩 나눠주면 1명의 인원이 이 보석을 받을 것이다. 그래서 백준 첫번째 예제의 경우 최대 4개의 보석을 가지도록 나눠주었을때, 총 3명의 인원이 보석을 갖게 된다. sum변수에 이값을 갖도록 했을때,
  sum>N이면, 최대로 줄 수 있는 보석의 개수를 너무 작게 잡았다는 뜻이므로, left를 mid+1로 갱신하여 준다.
  sum≤N이면, 최대로 줄 수 있는 보석의 개수가 더 작게도 가능하다는 뜻이므로, right 를 mid-1로 갱신하여 준다.
• 핵심 코드

  while(right-left>1){
              int mid = (right+left)/2;
              sum = 0;
              for (int i = 0; i < M; i++) {
                  sum+= Math.ceil((double)arr.get(i)/mid);
                  if(sum>N) break;
              }
              if(sum>N){
                  left = mid;
              }else{
                  answer = mid;
                  right = mid;
              }
          }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.util.*;
  import java.io.*;
  
  public class boj2792 {
      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());
          List<Integer> arr = new ArrayList<>();
          for (int i = 0; i < M; i++) {
              arr.add(Integer.parseInt(br.readLine()));
          }
          Collections.sort(arr,Collections.reverseOrder());
          int right = arr.get(0);
          int left = 1;
          int sum = 0;
          int answer = 0;
          int mid = 0;
          while(left<=right){
              mid = (right+left)/2;
              sum = 0;
              for (int i = 0; i < M; i++) {
                  sum+= Math.ceil((double)arr.get(i)/mid);
              }
              if(sum>N){
                  left = mid+1;
              }else{
                  answer = mid;
                  right = mid-1;
              }
          }
          System.out.println(answer);
      }
  }

결과