[BOJ] 보석 상자(2792)

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

문제 : BOJ_2792번 보석 상자

문제 설명

이분탐색

이분 탐색으로 해결할 수 있는 문제입니다.

사람 수 N이 있고, 보석의 종류 수 M이 있습니다.

한 사람에게는 한 종류의 보석을 나눠 줄 수 있고, 모든 사람에게 보석을 줄 필요는 없지만, 모든 보석은 나누어줘야 합니다.

이때, 보석을 가장 많이 갖고 있는 사람의 보석 수를 질투심이라고 할 때, 질투심의 최솟값을 구하는 문제입니다.

---

Solution

질투심을 최소로 하려면, 보석의 종류와 상관없이, N 명이 넘어가지 않으면서, 한 학생에게 나누어줄 수 있는 보석의 수의 최솟값을 구해야 합니다.

그러므로, 보석 수를 증가시키면서, 모든 보석을 N명 이하의 학생에게 나눠줄 수 있는지를 이분 탐색을 통해 찾아야 합니다.

이렇게 찾은 나눠주는 보석 수가 최소의 질투심이 됩니다.

---

Description

N명을 계산할 때, 보석의 수와 나눠주는 보석의 수가 나누어떨어지지 않는다면, 카운트에 1을 더해주어야 합니다.

---

#include <iostream>
#include <vector>
using namespace std;
int N, M, num,result;
vector<int> adj;
int main(void) {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int value;
        cin >> value;
        adj.push_back(value);
    }
    int le = 1;
    int ri = 1000000001;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        long long cnt = 0;
        for (int i = 0; i < M; i++) {
            cnt += (adj[i] / mid);
            if (adj[i] % mid) cnt += 1;
            // 나누어 떨어지지 않으면 +1
        }
        if (cnt <= N) {
            result = mid;
            ri = mid - 1;
        }
        else le = mid + 1;
    }
    cout << result<< '\n';
    return 0;
}