[BOJ] 2792 보석상자

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

이진탐색(binary search)을 이용하는 문제이다.

푸는 방법:

‘left = 1(보석 1개)’, ‘right = 가장 많은 보석수’로 설정한다.

‘mid = (left + right) / 2’인데, mid가 한 사람이 받은 가장 많은 수의 보석(=질투심)이다.

이제 질투심 = mid 일때, 보석을 나눠줄 수 있는 사람의 최소값을 계산해야한다.

최소 인원수 계산 방법은 아래와 같다.

‘cnt += (보석수) / mid’하고, 만약 보석의 수가 mid로 나누어 떨어지지 않으면 ‘cnt++’를 해준다.

cnt++은 보석에서 mid의 배수만큼 빼고 남은 보석들을 한 명이 다 가져가는 것을 의미한다.

위의 과정을 ‘can_divide’라는 함수를 만들어서 처리해줬고, 만약 cnt <= N이면 true를, 아니면 false를 반환해줬다.

cnt가 나눠줄 수 있는 사람의 최소수인데, N이 이거보다 작으면 해당 mid값일 때 나눠줄 수 없다.

can_divide의 반환값이 true이면 현재 mid값을 저장해놓고 right = mid-1로 바꾸어 이진탐색을 계속한다.

질투심을 현재보다 더 내려보려는 시도이다.

반환값이 false라면 질투심을 현재보다 올려야한다. 따라서 left = mid+1로 바꾸어 이진탐색을 계속한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

vector<ll> j;

bool can_divide(ll N, int mid) {
    ll cnt = 0;
    for(int i=0; i<j.size(); ++i) {
        cnt += j[i] / mid;
        if(j[i] % mid != 0) cnt++;
    }

    if(cnt <= N) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
  
    ll N;
    int M;
    cin >> N >> M;

    for(int i=0; i<M; ++i) {
        ll tmp;
        cin >> tmp;
        j.push_back(tmp);
    }

    ll right = *max_element(j.begin(), j.end());
    ll left = 1;

    ll ans;
    while(left <= right) {
        ll mid = (right + left) / 2;

        if(can_divide(N, mid)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

---