[c++] 1654 랜선 자르기 (파라메트릭 서치(Parametric Search))

파라메트릭 서치(Parametric Search)

이진 탐색과 다르게 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘

 

(하다 보니 이진 탐색과 고냥 거의 똑같다._.)

 

자료형은 처음에 unsigned int로 했다가 더하면 overflow 날 것 같아서 그냥 unsigned long long으로 했는데.

long long으로 다들 하더라카더라.. ㅇㅅㅇ

 

주의해야 할 것은 while문 안의 조건문에서 mid + 1, mid - 1을 넣어주었으니

while문 탈출 조건을 minLength < maxLength 가 아닌

minLength <= maxLength로 해야 한다는 것

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef unsigned long long ull;

int K, N;
ull input, minLength, maxLength, mid, res;
vector<ull> lan;

int countOfLan(ull length) {
    int cnt = 0;
    for (int i=0; i<K; i++) {
        cnt += lan[i] / length;
    }
    return cnt;
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> K >> N;
    for (int i=0; i<K; i++) {
        cin >> input;
        lan.push_back(input);
    }
    sort(lan.begin(), lan.end());
    
    // 랜선의 길이를 left, right, mid
    minLength = 1;
    maxLength = lan[K-1];
    mid = lan[K-1];
    
    while (minLength <= maxLength) {
        mid = (minLength + maxLength) / 2;
        if (countOfLan(mid) >= N) {
            res = mid;
            minLength = mid + 1;
        }
        else {
            maxLength = mid - 1;
        }
    }
    cout << res << "\n";
    return 0;
}