[ BOJ 백준 1654번 - 랜선 자르기 ] 해설 및 코드

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

 

 

 

목적

K개의 랜선을 최대 길이로 잘라 N개의 랜선을 만들자.

 

접근법

1. 길이를 1늘리거나 1줄이는 방법으로는 시간초과에 걸릴 것이다. 이분 탐색 알고리즘을 이용하자. (이분 탐색 과정 참고 : 백준 2110 - 공유기 설치)

2. 주어진 조건에 의해 int 자료형의 범위를 벗어나는 경우가 존재하기 때문에, 더 큰 범위의 자료형을 사용한다.

 

#include<iostream>
using namespace std;
 
int k,n,a[10001],ret;
 
void bs(unsigned l,unsigned r){
    if(l>r){
        ret=r;
        return;
    }
    
    unsigned h=((unsigned)l+r)/2;
    
    long long cnt=0;
    for(int i=0;i<k;++i) cnt+=(a[i]/h);
    
    if(cnt>=n) bs(h+1,r);
    else bs(l,h-1);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>k>>n;
    int tmp=0;
    for(int i=0;i<k;++i){
        cin>>a[i];
        if(tmp<a[i])tmp=a[i];
    }
    
    bs(1,tmp);
    cout<<ret;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.