BOJ. 1654

#BOJ1654

랜선 자르기

이 문제는 파라메트릭 서치를 사용해서 해결하는 문제이다. 멋있게 말하면 저렇게 되지만 간단하게 말하면 이분탐색이다. 이분 탐색은 정렬된 상황에서만 가능한데 1 - 10 까지에서 7을 찾고자 할 때, 1 과 10의 중간인 5로 가서 7보다 큰 지 작은지를 통해서 7을 찾는 과정이다. 이 과정은 그냥 하나하나 확인할때는 최악의 상황에서 원소의 갯수인 N개를 확인해야 하지만 이분 탐색을 사용하면 logN만 사용하면 되므로 시간적으로 매우 유리하다. 아 추가로 이 문제가 정답률이 매우 낮은데 int를 선언할 때 unsigned를 붙여주면 대부분의 상황 문제를 해결할 수 있다. 이분 탐색 관련 문제가 여러 개 있어서 한 번에 다 풀어보려고 한다.

# include <iostream>
# include <algorithm>
using namespace std;

unsigned int N, K, max_temp = 0, l = 1, r = 0, m, ans = 0;

int main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   
   cin >> K >> N;
   
   unsigned int* arr = new unsigned int[K];
   for (int i = 0; i < K; i ++){
       cin >> arr[i];
       max_temp = max(max_temp, arr[i]);
   }
   r = max_temp;
   while (l <= r){
       unsigned int temp = 0;
       
       m = (l + r) / 2;

       for (int i = 0; i < K; i++){
           temp += arr[i] / m;
       }

       if (temp >= N){
           l = m + 1;
           ans = max(ans, m);
       }
       else r = m - 1;

   }
   cout << ans << "\n";

}