BOJ 2792 : 보석상자

풀이 상세

parametric search

풀이 요약

1. 인원 $N$ 명과 각각의 수가 존재할 때, 어떻게 나눠야 $N$ 명이 고루 분배될 수 있는지 찾아야 한다.

2. 이분탐색을 활용한다. $mid$ 를 기준으로 모든 보석을 나누어준다. 각 보석을 $mid$ 만큼 나누어줄 때 받을 수 있는 인원은 $j/mid$ 이며 나머지가 존재하는 경우라면 $j/mid+1$ 이 된다. 각 보석을 $mid$ 를 기준으로 제공했을 때 현재 인원을 넘지 않은지 확인한다.

3. 현재 인원을 넘는 경우라면 제공하는 보석여부가 남는 경우이므로, $mid$ 값을 올려주고, 반대라면 $mid$ 값을 줄여준다.

4. 문제에서 원하는 답은 모두에게 고루 분배해줄 수 있는 최소의 값을 찾는 것이다. 또한 누군가가 안받는 경우도 허용하기 때문에, lower_bound 에 기인한다.

배운점

• parametric search (매개 변수 탐색) 에 대해 알게 되었다. 더불어 “어? 이게 이분탐색으로 된다고?” 하는 것들이 대부분 parametric search 라는 것을 알게 되었다.

• parametric search 는 최적화 문제를 결정 문제로 뒤바꾸는 효율성 공식 문제이다.

#include <iostream>

using namespace std;
typedef long long ll;
ll N, M, arr[300000+4], ans = 1e18;

bool check(ll mid) {
    ll num = 0;
    for (int i = 0; i < M; i++) {
        num += arr[i] / mid;
        if(arr[i] % mid) num++;
    }
    return N >= num;
}

int main() {
    cin >> N >> M;
    ll l = 1, r = 0;
    for (int i = 0; i < M; i++) cin >> arr[i], r = max(arr[i], r);
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            ans = min(ans, mid);
            r = mid-1;
        } else {
            l = mid+1;
        }
    }
    cout << ans;
}