Beakjoon 1654 랜선 자르기

05 Feb 2021 in Algorithm

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

나의 풀이

오영식이 가지고 있는 i번째 랜선의 길이를 K_i라고 하고, 박성원이 N개를 만들 수 있는 랜선의 길이를 L이라고 할 때 N은 다음과 같이 표현 할 수 있다. K_1/L + K_2/L + K_3 …. + K_k/L >= N

이 문제에서 구하고자 하는 것은 위 조건을 만족하는 L의 최댓값을 찾는 것이다. L의 값은 1부터 K_i의 최댓값 이하이기 때문에 이 범위 사이에서 이진 탐색을 하여 L이 위 조건을 만족하는지 확인해나가며 문제를 해결 할 수 있다.

랜선의 길이는 최대 2^31-1 이기 때문에 int형 범위를 넘어가지 않지만 (left+right) 과정에서 int형 범위를 넘어가 오버플로우가 발생할 수 있다는 점을 주의해야한다.

풀이 코드 : 1654 랜선 자르기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, num, max_ = -1;
    cin>>K>>N;

    vector<int> lan;
    for(int i=0;i<K;i++){
        cin>>num;
        lan.push_back(num);
        if(max_ < num) max_ = num;
    }

    long long left = 1;
    long long right = max_;
    int answer = 0;
    while(left <= right){
        long long mid = (left+right)/2;
        if(mid == 0) break;
        int total = 0;

        for(int i=0;i<K;i++){
            total += (lan[i]/mid);
        }

        if(total >= N){
            answer = mid;
            left = mid + 1; 
        }
        else{
            right = mid - 1;
        }
    }

    cout<<answer;

}

채점결과