16401_과자 나눠주기

사용 알고리즘: 이분 탐색

사용 언어: java

 

package week21;

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

public class Main {
	static int n, m;
	static int[] arrs;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		m = sc.nextInt(); //조카 수
		n = sc.nextInt(); //과자 수
		
		arrs = new int[n];
		for(int i=0; i<n; i++) {
			arrs[i] = sc.nextInt();
		}
		Arrays.sort(arrs);
		
		int left = 1;
		int right = arrs[n-1];
		int ans = 0;
		while(left <= right) {
			int mid = (left+right) / 2;
			int sov = solve(mid);
			if(sov >= m) {
				left = mid +1;
				ans = mid;
			} else {
				right = mid - 1;
			}
		}
		
		System.out.println(ans);
	}

	private static int solve(int mid) {
		int cntBabies = 0;
		for(int i=0; i<n; i++) {
			cntBabies += arrs[i] / mid;
		}
		return cntBabies;
	}

}