[BS] 백준 2792 보석 상자

• 최대로 나누어 준다고 가정하고 풀면 되는 문제
• 왜냐하면 일단 최대로 나눠줄 수 있으면 못 나눠준 것 들은 최대로 나눠 준 것에서 한개씩만 빼서 줘도 결과엔 영향이 없기 때문이다.

#include <iostream>

#include <algorithm>

#include <limits>

using namespace std;

typedef long long ll;

ll tb1[300001];

ll allsum = 0;

ll maxv = 0;

ll n, m;

//int maxidx;

bool ok(ll mid) {

       ll sum = 0;

       for (int i = 0; i < m; ++i) {

              sum += (tb1[i] - 1) / mid + 1; // tb1[i] -1 한다음 다시 +1 => 홀수 처리

       }

       return sum <= n;

}

int main(void) {

       

       cin >> n >> m;

       for (int i = 0; i<m; ++i) {

              cin >> tb1[i];

              allsum += tb1[i];

              maxv = max(maxv, tb1[i]);

       }

       ll left = 1;

       ll right = maxv;

       while (left <= right) {

              int mid = left + (right - left) / 2;

              if (ok(mid)) {

                     right = mid-1;

              }

              else {

                     left = mid + 1;

              }

       }

       cout << left << endl;

       return 0;

}