[백준/C,C++] 1654번: 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

풀이

이분 탐색으로 푸는 문제입니다.

 

예제 입력으로 보면

 

4 11

802

743

457

539

 

에서 1을 최소로, 802(가장 큰 값)를 최대로 두고 이분 탐색을 시작하면 되는데,

 

조건은 해당 값으로 존재하는 랜선을 모두 나누었을 때 필요한 랜선의 개수만큼 나오는지 체크하면 됩니다.

 

#include<iostream>
#include<vector>

using namespace std;

using LL = long long;

const int MAX = 10000;

int k, n;
vector<LL> lan(MAX);
LL res;

bool check(LL l)
{
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        cnt += (lan[i] / l);
    }
    if (cnt >= n) return true;
    else return false;
}

LL search(LL start, LL end)
{
    if (start > end) return res;
    LL mid = (start + end) / 2;
    if (check(mid)) {
        res = max(res, mid);
        return search(mid + 1, end);
    }
    else return search(start, mid - 1);
}

int main(void)
{
    cin >> k >> n;

    LL m = 0;
    for (int i = 0; i < k; i++) {
        cin >> lan[i];
        m = max(m, lan[i]);
    }

    cout << search(1, m);

    return 0;
}

 

check 함수가 지금 탐색 중인 값으로 랜선들을 나누었을 때 필요한 만큼 나오는지 체크하는 함수이고,

 

search 함수는 이분 탐색함수입니다.

 

초깃값으로는 1과 가장 긴 랜선이 전달됩니다.

반례

Input

2 10

200

400

Output

57

 

Input

3 100

555

324

178

Output

10