[BOJ/C++] 랜선 자르기(1654번)

1. 개요

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

1654번: 랜선 자르기

1-1. 설명

캠프에서 쓸 N개의 랜선을 만들어야 한다. 이미 자체적으로 K개의 랜선을 지니고 있으나, K개의 랜선 길이는 제각각이다. N개의 같은 길이 랜선을 만들기 위해 K개의 랜선을 잘라 만들어야 한다. 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이가 없다고 가정하고, 기존 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것 또한 포함된다. 이때 만들 수 있는 최대 랜선 길이를 구하는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에는 이미 가지고 있는 랜선 개수 K, 필요한 랜선 개수 N이 입력되며 K는 1 이상 10,000이하 정수, N은 1 이상 1,000,000 이하 정수고, 항상 K <= N

 - K줄에 걸쳐 이미 가지고 있는 각 랜선 길이가 센티미터 단위 정수로 입력되며 랜선의 길이는 2^31-1이하 자연수

---

2. 구현

2-1. 풀이

이분 탐색을 통해 자른 랜선의 개수를 구하여 최대 길이를 저장한다. 주의할 점은 데이터 타입이다. integer는 오버플로우가 일어나므로, 반드시 long long을 사용해야 한다. 

2-2. 코드

#include <iostream>
#include <algorithm>
using namespace std;

constexpr size_t MAX_NUM = 10000;
long long wire[MAX_NUM];
long long result = 0;
int N, K;

void binarySearch(long long first, long long last);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> K >> N;

    for (int i = 0; i < K; i++) cin >> wire[i];
    sort(wire, wire + K);

    binarySearch(1, wire[K - 1] + 1);
   
    cout << result;
    return 0;
}

void binarySearch(long long first, long long last) {
    if (first >= last) return;
    long long mid = (first + last) / 2, cnt = 0;
    for (int i = 0; i < K; i++) cnt += wire[i] / mid;
    if (cnt < N) binarySearch(first, mid);
    else if (cnt >= N) {
        result = max(result, mid);
        binarySearch(mid + 1, last);
    }
}