[세모] 백준 2792 보석상자 // 이분탐색, 매개변수탐색

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

* 풀이

 

• 헤맸던부분
  • 질투심이 x 일때, 학생수를 계산하는 idea
  • 그림으로 그려보자
  • st,en을 디버깅 찍어가면서 수정 (st+en) or (st+en+1)

#include<bits/stdc++.h>
using namespace std; 

int n,m;
int a[300000+4];

int go(int x) {
   int cnt=0; // 필요한 학생수
   for(int i=0;i<m;++i) {
      cnt += (a[i]/x);
      if(a[i]%x !=0 ) { // 나머지가있는경우 +1 해줘야함 (올림)
         cnt++;
      }
   }
   return cnt <= n;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

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

   int st=1;
   int en=pow(10,9);
   while(st<en) {
      int mid = (st+en)/2;
      // cout<<st<<" "<<en<<" \n";
      if(go(mid)) {
         en=mid;
      }
      else {
         st=mid+1;
      }
   }

   
   cout<<st;
}