[백준 1654]알고리즘 55일차 : 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

이분 탐색 C++

문제 보고 어디에 이분탐색을 써야하는지 고민했던 문제

힌트로 parametric search 라고 돼있어서 개념 찾아봤는데 별 도움은 안됐음..

1부터 max 길이 까지를 범위로 두고 그 안에서 랜선 길이를 이분 탐색하면서 찾아가는 거였다.

처음엔 랜선 개수를 계산하는게 시간이 오래걸릴 것 같아서 그걸 이분 탐색으로 대체해야하나 싶었는데

그 부분은 그냥 계산돌려도 되는 거였음 (진짜 나만 알아듣는 언어..)

 

확실히 종이에 풀고 코드로 쓰니까 코드가 덜 복잡해진다..

접근방법

1~max까지의 숫자 중 하나를 이분 탐색으로 탐색한 후 그 숫자가 랜선 길이라고 생각하고 최대 랜선 개수를 구함

개수가 N보다 크거나 같으면 (랜선이 충분히 많이 나오면) 길이를 늘려감, 개수가 N보다 작으면 (랜선 개수 부족) 길이를 줄여감 (이분탐색)

 

오답노트 

처음 코드에서 틀렸던 부분은 int를 long long으로 안한거, 최솟값 0으로 시작한거 (1로 시작해야함)

코드 잘 짜면 N이 1일때 예외처리 필요없음

그리고 가장 크리티컬했던건 

while(s <= e) 이부분 .. s < e 로 하면 안됨

왜냐면 200 200 201 일때 n n n-1 이라면 s e - 이렇게 되면 그 다음 차례엔 - s,e - 이렇게 되는데 반복문 조건이 s<e이면 저상태로 빠져나와서 s가 200이 되고 s-1이 되니까 199가 되는데 그럼 안됨 그래서 s=e일때도 반복문 들어가게 해줘서 - e s 로 넘겨줘야 됨

그거만 바로 잡았어도 첫번째 코드로 통과할 수 있었는데 ^^..40분동안 헤맸음

 

소스코드

#include <iostream>
using namespace std;
long long lengths[10000];
int K, N;

bool isOverN(long long len){
    int cnt = 0;
    for(int i = 0 ; i < K ; i++)
        cnt += lengths[i]/len;
    return cnt>=N ? true : false;
}
long long binarySearchMax(long long s, long long e){
    long long mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if(isOverN(mid)){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return s-1;
}
int main(){
    cin >> K >> N;
    long long max = 0;
    for(int i = 0 ; i < K ; i++){
        cin >> lengths[i];
        max = ( max <= lengths[i] ? lengths[i] : max );
    }
    cout << binarySearchMax(1,max);
    
    return 0;
}