[이진 탐색] 백준 1654 랜선 자르기 C++

 

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

1654번: 랜선 자르기

 

#include<iostream>

using namespace std;

int n, k;
long long ans;
int num[10001];

void binarySearch(long long s, long long e) {
    while (s <= e) {
        long long m = (s + e) / 2;  // 자료형 조심(매개 변수까지)
        
        long long temp = 0;
        for (int i = 0; i < k; i++) {
            temp += (num[i] / m);
        }
        
        if (temp >= n) {  // n개 이상 포함할 때
            ans = max(ans, m);
            s = m + 1;
        }
        else e = m - 1;

    }
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> k >> n;

    int temp = 0;
    for (int i = 0; i < k; i++) {
        cin >> num[i];
        temp = max(temp, num[i]);
    }
    
    binarySearch(1, temp);  // 1부터 시작
    cout << ans;

    return 0;
}