[ 백준 C++ ] 1654번 랜선 자르기 (파라메트릭 서치)

문제 

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

1654번: 랜선 자르기

파라메트릭 서치 

최적화 문제( 최소/최대값 구하는 문제 ) -> 결정 문제 바꾸어푸는 것.

그냥 탐색으로 풀면 시간초과를 받는다. 탐색인데 수가 크다면 의심해보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <queue>
#include <cstring>


using namespace std;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k,n;
    long long min=1;
    long long max =0;
    long long mid =0;
    long long sum =0;
    long long answer=0;
    cin >> k>>n;
    
    vector<long long> v;
    
    for(int i=0; i<k; i++)
    {
        int tmp =0;
        cin >> tmp; 
        v.push_back(tmp);
    }
    max = *max_element(v.begin(),v.end());
   
    
    while(min <=max)
    {
        mid = (min +max)/2;
        sum = 0;
        for(int i=0; i<k; i++)
        {
            sum += (v[i]/mid);    
        }
        if(sum >=n)
        {
            answer = mid;
            min = mid+1;
        }else
        {
            max = mid-1;
        }
    }
    cout << answer;
    return 0;
    
}