백준 6236 용돈 관리 ( C++ )

문제

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

 

해설

인출 횟수가 n보다 작기만 하면 되는 문제

이분 탐색을 이용

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
typedef long long ll;
 
int n,m,cost,mx;
ll ret, low,hi,mid;
vector<int> v;
 
bool go(int num){
  ll tmp=1,tmp_cost = 0;
  for(int i : v){
    if((tmp_cost + i)<=num){
      tmp_cost+= i;
    }
    else{
      tmp_cost = 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 >> cost;
    mx = max(mx,cost);
    hi += cost;
    v.push_back(cost);
  }
 
  low = mx;
  while(low<=hi){
    mid = (low+hi)/2;
    if(go(mid)){
      hi = mid-1;
      ret = mid;
    }
    else{
      low = mid+1;
    }
  }
 
  cout << ret;
  return 0;
}