[C++] 백준 #1654 랜선자르기

문제 링크

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

1654번: 랜선 자르기

 

풀이

이분 탐색 문제이다.

나는 탐색 범위 왼쪽을 pl, 중간을 pc, 오른쪽을 pr로 두고 풀었다.

 

<틀린 풀이>

처음에는 맨 처음 탐색 범위가 1부터 배열에서 가장 작은 수인 줄 알았다.

그렇게 소스 코드를 짰고, 결과는 시간초과가 났다.

아마 테스트케이스 중에 가장 작은 수보다 랜선의 길이가 커야 할 때가 있는 것 같았다.

그래서 계속 재귀함수 안으로 안으로 들어가다 보니 시간 초과가 난 것 같다. (처음엔 재귀함수로 구현)

 

<고친 풀이>

그래서 맨 처음 탐색 범위를 1부터 가장 큰 수로 고쳤다.

그리고 나서 

1. 중앙 값으로 계산했을 때 나오는 랜선의 개수를 구하기
2. 그 개수보다 K가 더 큰 경우에는 -> 개수를 늘려야 하니까 범위를 현재보다 오른쪽으로 (pl은 pc-1, pr은 그대로)
   개수가 K보다 더 큰 경우에는 -> 개수를 줄여야 하니까 범위를 현재보다 왼쪽으로 (pl은 그대로, pr은 pc-1)

하지만 그래도 틀렸습니다가 떴다.

 

계속해서 생각해보니,

이분 탐색으로 범위로 계산하다 보니까 현재 구한 중앙값(랜선 길이)이 최대 랜선 길이가 아니라는 것을 깨달았다.

결국 랜선의 개수가 K개가 되더라도 그때의 랜선길이가 최대가 아닐 수 있으니, pl<=pr 일 동안에는 계속해서 구해야한다.

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/08/04.
//

#include <iostream>
#include <algorithm>
using namespace std;
int K, N;
int lines[10001];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>K>>N;
    for(int i=0; i<K; i++){
        cin>>lines[i];
    }
    sort(lines, lines+K);
    int ans = 0;

    long long pl=1, pr=lines[K-1];
    long long pc;
    while(pl<=pr){
        pc=(pl+pr)/2;
        int cnt = 0;
        for(int i=0; i<K; i++){
            cnt+=(lines[i]/pc);
        }
        if (cnt>=N) {
            pl = pc+1;
            if(ans < pc) ans = pc;
        }
        else {
            pr = pc-1;
        }
    }
    cout<<ans<<"\n";
}