1654번_랜선 자르기_BOJ

문제 링크

1654번 랜선 자르기 : https://www.acmicpc.net/problem/1654

문제 설명 및 해결 아이디어

Parametric Search문제이다.

이때 right는 10,000,000,000으로 해야한다.

mid는 랜선 길이로 설정한다.

특정 mid값으로 만들 수 있는 랜선의 개수가 주어진 N보다  작을 경우, mid값을 작게하여 랜선의 개수를 늘릴 수 있다.

반대의 경우, mid값을 크게하여 랜선의 개수를 줄일 수 있다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX_S 10001
#define ll long long int
ll k, n, res;
ll line[MAX_S];
 
void func() {
    ll left = 1, right = 10000000000LL;
 
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll ret = 0;
        for (int i = 0; i < k; ++i) {
            ret += (line[i] / mid);
        }
 
        if (ret < n) {
            right = mid - 1;
        }
        else if (ret >= n) {
            left = mid + 1;
            res = max(res, mid);
        }
    }
}
int main() {
    scanf("%lld %lld", &k, &n);
    for (int i = 0; i < k; ++i)
        scanf("%lld", &line[i]);
    res = -987654321;
    func();
    printf("%lld\n", res);
 
    return 0;
}