문제 푼 날짜 : 2021-07-14

문제

문제 링크 : https://www.acmicpc.net/problem/1654

접근 및 풀이

나무자르기 문제(https://www.acmicpc.net/problem/2805)와 비슷한 문제였다.
랜선을 자르는 길이의 범위를 (1 ~ 가장 긴 랜선 길이) 로 정하고, (1 + 가장 긴 랜선 길이)/2를 기준으로 각각 랜선마다 몇 개씩 자를 수 있는지 체크해주었다.

코드

// 백준 1654번 : 랜선 자르기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int K, N;
vector<long long> wire;

int check(long long base) {
    int sum = 0;
    for (int i = 0; i < K; i++) {
        sum += (wire[i] / base);
    }
    return sum;
}

long long BinarySearch() {
    long long ans = 0;
    long long low = 1, high = wire[K - 1];

    while (low <= high) {
        long long mid = (low + high)/2;

        if (check(mid) >= N) {
            ans = max(ans, mid);
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> N;

    for (int i = 0; i < K; i++) {
        long long length;
        cin >> length;
        wire.push_back(length);
    }
    sort(wire.begin(), wire.end());

    cout << BinarySearch() << '\n';
    return 0;
}

결과

피드백

어렵지 않은 기본적인 이진 탐색 문제였고, 어려운 문제도 풀어봐야할 듯하다.