[BOJ] 1654번 랜선 자르기

문제 바로가기

접근

바로 이전 글의 나무 자르기와 아주 유사하다. 중간값을 자르고자 하는 랜선의 길이로 두고 랜선을 잘라본다. 그리고 그 랜선의 길이가 최대가 될 때를 구하면 된다.

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

#define MAX 10000

long long K, N;
long long cable[MAX] = {0};
int result = 0;

long long bsearch(long long low, long long high) {
  long long mid = (low + high) / 2;
  int cnt = 0;

  if(low > high) return result;

  for(int i = 0; i < K; i++)
    cnt += cable[i] / mid;

  if(cnt >= N)
    result = result < mid ? mid : result;

  if(cnt >= N)
    return bsearch(mid + 1, high);
  else
    return bsearch(low, mid - 1);
}

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

  cin >> K >> N;
  for(int i = 0; i < K; i++)
    cin >> cable[i];
  sort(cable, cable + K);

  bsearch(1, cable[K - 1]);
  cout << result;
}