백준 2792번 : 보석상자

문제링크 : https://www.acmicpc.net/problem/2792

2792번: 보석 상자

 문제설명 

 

1. 유치원 생 수와 보석의 종류 수가 주어지고 보석의 종류별 숫자가 주어진다.

2. 가장 많은 보석을 가지고있는 유치원생이 가지고있는 보석의수가 질투심의 수치이다.

3. 질투심의 수치가 최소가 되게 보석을 나눠주는 방법을 찾아 최소 질투심의 수치를 출력하라.

 

 알고리즘 

 

1. 이분탐색을 통해 최소 질투심을 찾는다.

2. 처음에 high 를 보석의 종류중 가장많은 갯수로 두고 low = 1로 둔다.

3. 그리고 질투심에 맞게 보석수를 나눠줄수 있으면 high = mid-1 로 두고 아니면 low = mid +1 로두어 이분탐색을

  진행한다.

 

 코드 

 

#include<iostream>
#include<algorithm>
 
 
using namespace std;
typedef long long ll;
 
 
int N, M;
int color[300001];
bool check(int n) {
    int num = 0;
    for (int i = 0; i < M; i++) {
        int a = color[i] / n;
        int b = color[i] % n;
        
        num += a;
 
        if (b)     num ++;
    }
    if (num <= N)return true;
    return false;
}
 
int main() {
 
    cin >> N>>M;
 
 
    int high=0, low = 1;
 
    for (int i = 0; i < M; i++) {
 
        cin >> color[i];
 
        if (high < color[i]) 
            high = color[i];        
        
    }
 
    while (low <= high) {
        int mid = (low + high) / 2;
 
        bool pos = true;
 
        if (!check(mid)) pos = false;
 
 
        //보석이 남지않을때
        if (pos) high = mid - 1;
 
        //보석이 남을 때
        else  low = mid + 1;
            
        
    }
    cout << low;
    
 
}