백준 1654 랜선자르기 c++ // 이분탐색, parametric search

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

1654번: 랜선 자르기

1. parametric search

최적화문제 -> 결정문제로 바꿔서 해결한다.

단, 감소또는 증가함수에서만 사용가능하다.

이경우에는 랜선길이up => 랜선갯수down 이다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

N개로만들수있는 랜선의 최대길이 -> 랜선길이가x일때, 랜선갯수가 N개이상인가?

 

2.의사코드

while (st < en) {
        ll mid = (st + en + 1) / 2; //이래야 무한루프안됨
        if (go(mid)) st = mid; //랜선을자를수있으면 -> 더큰길이로잘라도되는지 우측탐색
        else en = mid - 1; //랜선을 못자르면 -> 랜선길이를줄여야함 -> 좌측탐색
    }

 

3.이분탐색

for(0~2^31==21억) -> 시간초과 -> st,en을 두고 이분탐색을 구현한다.

 

4. 전체코드

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

typedef long long ll;
ll k,n,a[10000+4];

//길이가 x일때, 랜선이n개이상일수 있는지
int go(ll x) {
    ll cur = 0; //x개로 랜선자른 갯수
    for (int i = 0; i < k; ++i) cur += a[i] / x;
    return cur >= n;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> k>> n;
    for (int i = 0; i < k; ++i) {
        cin >> a[i];
    }


    ll st = 1, en = (1<<31)-1;
    while (st < en) {
        ll mid = (st + en + 1) / 2;
        if (go(mid)) st = mid; //랜선을자를수있으면 -> 더큰길이로잘라도되는지 우측탐색
        else en = mid - 1; //랜선을 못자르면 -> 랜선길이를줄여야함 -> 좌측탐색
    }
    cout << st;

    return 0;
}