백준 2792번 보석 상자 ( C++ )

문제

https://www.acmicpc.net/problem/2792

 

해설

경우의 수가 너무 많기 때문에 이분탐색을 통해 logn만큼만 탐색하도록 함

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
typedef long long ll;
 
ll n,m,color_cnt,ret = 1e18;
vector<int> v;
 
bool go(int mid){
  ll tmp = 0;
  for(int i : v){
    tmp += i/mid;
    if(i%mid != 0)
      tmp++;
  }
  return n<tmp;
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
 
  ll low=1,high=0,mid;
  cin >> n >> m;
  for(int i=0;i<m;i++){
    cin >> color_cnt;
    v.push_back(color_cnt);
    high = max(high,color_cnt);
  }
 
  while(low<=high){
    mid = (low+high)/2;
    if(go(mid)){
      low = mid+1;
    }
    else{
      high = mid-1;
      ret = mid;
    }
  }
 
  cout << ret;
  return 0;
}