[백준 BOJ] 2792 보석상자 C++

문제 요약

Input

• 사람의 수 N, 보석 종류 수 M
• K번 색상 보석의 개수

Output

• 질투심의 최솟값
  • 즉, 질투심은 가장 많은 보석을 가져간 학생의 보석 개수

Contraints

• 한 사람에게 한 종류의 보석만 나눠준다.
• 모든 사람에게 보석을 나눠줄 필요는 없지만, 모든 보석을 나눠줘야 한다.

Edge Cases

• N의 범위는 1 ≤ N ≤ 10^9로 시간 복잡도를 줄이는 방법을 생각해야 함

---

문제 풀이

Solution

• 보석의 수를 증가시키면서 모든 보석을 N명 이하의 학생에게 나눠줄 수 있는지 여부를 이분 탐색을 통해 찾아야 함

 

#include <iostream>
#include <vector>
#define MAX 1000000001;
using namespace std;

int N,M,num,result;
vector <int> v;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;

    for (int i=0;i<M;i++){
        cin >> num;
        v.push_back(num);
    }

    int l=1; int r=MAX;
    while (l <= r) {
        int mid = (l + r)/2;
        long long cnt = 0;

        for (int i=0;i<M;i++){
            cnt += (v[i]/mid);
            if (v[i] % mid) cnt+=1;
        }

        if (cnt <= N){
            result = mid;
            r = mid-1;
        } else l = mid+1;
    }

    cout << result << '\n';

    return 0;
}