[백준 알고리즘] 1654번: 랜선 자르기

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

문제

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

나무 자르기 문제 처럼 이분탐색으로 풀 수 있는 문제였다. 이분 탐색으로 자를 랜선의 길이를 탐색하면서 해당 길이로 각 랜선들을 나눴을 때, 몫의 합이 K와 같게 만들면 된다.

한 가지 유의해야 하는 조건은 N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이다. 그리고 최대 길이를 구해야 하기 때문에, 일반 이분탐색 처럼 K와 일치하는 결과를 만드는 길이를 찾았다고 바로 끝내면 안되고, 가능한 경우를 모두 찾아보고 최대값을 사용해야 한다.

따라서 각 랜선을 현재 길이로 나눈 결과가 K보다 크기만 하면 무조건 후보로 삼고 이분탐색을 중간에 끝내지 않고 끝까지 진행한다. 이분탐색이 진행될수록 몫의 합은 K보다 크면서 K에 가까워지기 때문에 탐색이 모두 끝났을 때 가장 마지막으로 사용한 랜선의 길이가 최종 정답이 된다.

문제를 여러번 제출했다가 모두 틀렸습니다 를 받았는데, 변수의 자료형을 long long 으로 쓰지 않아서였다. 나무 자르기에서 이미 자료형의 범위를 유의해야한다는 것을 경험해서 문제를 잘 읽어봤는데, 랜선 하나의 길이가 int 형의 범위와 정확히 일치해서 괜찮을 것이라고 생각했지만 아니었다. 만약 길이를 1로 잡고 랜선을 자르게되면 int 최대 값 - 1의 길이를 가지는 랜선이 여러개 만들어지기 때문에 이 랜선들의 합은 long long 으로 표현해야 한다.

코드

' '
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> wires;

long long calcSum(long long c){
    long long sum = 0 ;
    for (long long wire : wires){
        sum += (wire/c);
    }

    return sum;
}

long long binarySearch(long long begin, long long end, long long target){
    long long mid = 0;
    long long answer = 0;
    while(begin <= end){
        mid = (begin + end) / 2;
        long long result = calcSum(mid);

        if (result >= target) {
            answer = mid;
            begin = mid + 1;
        }
        else if (result < target) end = mid - 1;
    }

    return answer;
}

int main (){
    long long K, N;
    long long longest = 0;
    scanf("%lld %lld", &K, &N);

    for (int i = 0 ; i < K ; i++){
        long long wire;
        scanf("%lld", &wire);

        wires.push_back(wire);
        longest = max(wire, longest);
    }

    printf("%lld", binarySearch(1, longest, N));
}