백준 2343번 기타 레슨 ( C++ )

문제

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

 

해설

이분탐색을 사용하는 문제

시작값이 가장 큰 강의의 길이가 되어야함

 

코드

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