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

2792번: 보석 상자 (acmicpc.net)

2792번: 보석 상자

---

난이도 : 실버2

 

해결 과정 :

이분 탐색으로 푸는 문제 였습니다.

나눠줄 때 한 색깔종류로만 나눠줘야 하기 때문에

각 색상의 개수 / 질투심 값과 나눴을 때 나머지가 나온다면 +1 해서 각각 더해진 cnt 값이

학생의 수와 같으면 right 값을 줄여주는 식으로 구현 하였습니다.

맨 첨에 left값을 0으로했다가 100퍼에서 틀렸다고 나오길래 1로 고쳐줬습니다.

 

코드 :

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int n, m, v[300005], ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> v[i];
    }
    sort(v, v+m);

    int l = 1, r = v[m - 1];
    while (l<=r) {
        int mid = (l + r) / 2;
        
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            cnt += v[i] / mid;
            if (v[i] % mid != 0) cnt++;
        }

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

    cout << ans;

}