BOJ 1654 - 랜선 자르기 / C++

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

1654번: 랜선 자르기

 

문제 풀이

이미 갖고 있는 랜선들 k개를 잘라 n개의 랜선을 만들 때, 랜선 하나의 최대 길이를 구하면 된다.

그러기 위해서는 랜선의 길이를 x라 했을 때, 원소들에 대해 (LANlines[i] / x)를 구하여 몇 개의 랜선을 만들 수 있는지 구한 뒤 모두 더해 n개 이상 만들 수 있다면 정답이 될 수 있다.

 

따라서 0부터 랜선의 최대 길이를 이분 탐색하며 랜선 하나의 길이를 임의로 정하고 최댓값 최솟값을 변경해나가며 랜선 하나의 최대 길이를 구한다.

 

소스 코드

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

int main(){
    int k, n; //이미 갖고 있는 랜선의 개수 k, 필요한 랜선의 개수 n
    vector<long long> LANlines;
    long long answer;

    cin >> k >> n;

    for(int i=0; i<k; i++){
        long long tmp;
        cin >> tmp;
        LANlines.push_back(tmp);
    }

    sort(LANlines.begin(), LANlines.end());

    long long st = 0;
    long long en = LANlines[k-1];

    while(st <= en){
        int cnt = 0;
        long long mid = (st + en) / 2;
        if(mid == 0){
            answer = 1;
            break;
        }

        for(int i=0; i<k; i++){
            if(LANlines[i] >= mid){
                cnt += (int)(LANlines[i] / mid);
            }
        }

        if(cnt >= n){
            answer = mid;
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }

    cout << answer;
}

 

시행 착오

만약 mid = 0이 된다면 DivisionByZero 에러가 발생하기 때문에 해당 경우를 예외처리해준다.