BOJ2792 보석상자

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

2792번: 보석 상자

 

check()함수 만드는 것이 꽤 생각을 요하는 문제

질투값이 널널하다면 그냥 true을 뱉으면 된다. 왜냐면 다음 탐색에서 정답을 찾기 때문에 최대한 빡세게 검사하고 보석을 다시 분배에서 사람수만큼의 집합으로 만든다고 생각하면됨

 

다시 문제를 보니 보석을 주지 않아도 되기 때문에 간단한 문제였다..

import java.util.*;
import java.io.*;
public class Main
{
    public static int n;
    public static int m;
    public static int[] input;
    
    public static boolean check(int num){
        int count=0;
        for(int i=0;i<n;i++){
            //각 보석을 가장 작은 수의 집합으로 만들기 -> 어차피 3,3,2 처럼 나누면 3이나 2은 더 작은 수로 더 많은 사람에게 나누어 줄 수 있기 때문에 상관x
            // 질투값보다 낮아져도 다름 이분탐색에서 찾을 수 있다.
            count+=input[i]/num;
            if(input[i]%num>0){
                count+=1;
            }
        }
        if(count<=m){
            return true;
        }else{
            return false;
        }
    }
    
    public static int search(){
        int l = 1;
        int r= 1_000_000_000;
        int ans = 0;
        while(l<=r){
            int mid = (l+r)/2;
            if(check(mid)){
                r=mid-1;
                ans = mid;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }
    
	public static void main(String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp1 = br.readLine().split(" ");	    
	    m= Integer.valueOf(temp1[0]);
	    n = Integer.valueOf(temp1[1]);
	    input = new int[n];
	    
	    for(int i=0;i<n;i++){
	        input[i] = Integer.valueOf(br.readLine());
	    }
	    int ans = search();
	    
		System.out.println(ans);
	}
}

import java.util.Scanner;

class Main
{
    public static boolean isPossible(int[] colorAmounts, int maxDivideCount, int totalStudentCount) {
        int receivedStudentCount = 0;
        for (int colorAmount : colorAmounts)
            receivedStudentCount += (colorAmount + maxDivideCount - 1) / maxDivideCount;
        return receivedStudentCount <= totalStudentCount;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] colorAmounts = new int[M];
        for (int i = 0; i < M; i++)
            colorAmounts[i] = sc.nextInt();

        int l = 1, r = 1000000000, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (isPossible(colorAmounts, m, N)) {
                ans = m;
                r = m - 1;
            }
            else l = m + 1;
        }
        System.out.println(ans);
    }
}