구슬 상자

구슬상자 (marblebox.cpp)

 

문제

---

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

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

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

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

입력

---

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

다음 M개 줄에는 1이상 1,000,000,000이하의 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 구슬의 개수이다.  

출력

---

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

예제 입력

5 2
7
4

예제 출력

3

 

출처

---

COCI 2012/2013 Contest #1 4번  

코드

///구슬상자

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long result = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int[] c;
        int d = 0;
        int count = 0;
        int max = Integer.MIN_VALUE;
        a = sc.nextInt();
        b = sc.nextInt();

        c = new int[b];

        for (int i = 0; i < b; i++) {
            c[i] = sc.nextInt();
            if (max < c[i]) max = c[i];
        }

        findNNumber(0, (long) max, c, a);

        System.out.println(result);
        sc.close();

    }


    public static long canGive(int[] arr, long a, long give) {
        long count = 0;
        for (int i = 0; i < arr.length; i++) {
            count = arr[i] / give;
            if (arr[i] % give != 0) count++;
            a -= count;
            if (a < 0) return -1;
        }

        return a;
    }

    public static void findNNumber(long s, long e, int[] arr, long target) {
        if (s > e) return;
        else {
            long mid = (s + e) / 2;
            long cnt = canGive(arr, target, mid);

            if (cnt == -1) findNNumber(mid + 1, e, arr, target);
            else {
                if (result > mid) {
                    result = mid;
                }
                findNNumber(s, mid - 1, arr, target);
            }
        }

    }


}