[C++] 백준 15732번 도토리 숨기기

문제

백준 15732번 도토리 숨기기

풀이

x번 상자를 택했을 때 x번 상자까지 들어간 도토리의 개수와 우리가 넣고자하는 도토리 개수 D를 비교해가며 이분탐색을 하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,k,d;
int a[10000];
int b[10000];
int c[10000];

bool decision(int box){
  long long cnt = 0;
  for (int i=0; i<k; i++){
    if (box < a[i]) continue;

    cnt += (min(b[i],box) - a[i]) / c[i] + 1;
  }

  return cnt >= d;
}

int solve(){
  int lo = 1;
  int hi = 1000000;

  while (lo <= hi){
    int mid = (lo+hi)/2;
    if (decision(mid)) hi = mid-1;
    else lo = mid+1;
  }

  return lo;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n >> k >> d;

  for (int i=0; i<k; i++){
    cin >> a[i] >> b[i] >> c[i];
  }

  cout << solve();
}