[BOJ/C++] 1654: 랜선 자르기

🥈 Silver 2

✏️ 최종 솔루션

⭐️ 이분 탐색

1. 랜선의 길이를 오름차순 정렬
2. 이분탐색을 위해 left는 1, right 는 최대 랜선 길이로 정의
3. left와 right 가 동일해질 때까지 반복해서 탐색
   1) 탐색할 때마다 left, right 가 갱신되기 때문에 mid 도 갱신해주고 시작
   2) 탐색할 때마다 모든 랜선을 mid 로 나눈 몫의 합계 count
   3) count 값이 k 보다 작으면 랜선 길이를 줄이고 개수를 늘려야하기 때문에 랜선 길이 범위를 낮추기 위해 right = m - 1 로 mid 앞 범위를 이어서 탐색하도록 조정
   4) count 값이 k 보다 크면 랜선 길이를 어디까지 늘릴 수 있는 지 확인하기 위해 랜선 길이 범위를 높여서 left = m + 1 로 mid 뒷 범위를 이어서 탐색하도록 조정
   이 경우의 랜선 길이는 정답이 될 수 있는 길이이기 때문에 정답 후보 중에 최대값을 ans 에 저장

📌 self feedback

이분 탐색을 무조건 두 범위로 나눠서 Mid 값과 대소비교하는 것으로 이해해서 풀이에 어려움 겪음
이분 탐색은 탐색 범위를 두 범위로 나눠서 탐색 범위를 좁혀나가며 정답에 근접해가는 방법임을 숙지하고 이분 탐색 유형 풀이가 더 필요

✏️ 최종 code

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

int main() {
    long long k,n;
    cin >> k >> n;

    long long mx=0;
    vector<long long> v(k);
    for(int i=0;i<k;i++) {
        cin >> v[i];
        mx=max(mx,v[i]);
    }

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

    long long l=1, r=mx,m,ans=0;

    while(l<=r) {
        m=(l+r)/2;
        long long cnt=0;
        for(int i=0;i<k;i++) {
            cnt+=v[i]/m;
        }

        // 개수가 작으면 길이 범위를 더 줄여서 탐색하기 위해 Mid 값 앞으로 Right 를 옮겨줘서 Mid 앞 범위 탐색
        if(cnt<n) r=m-1;
        // 개수가 크면 Mid 값 앞으로 Left 를 옮겨줘서 Mid 뒤 범위 중에서 개수가 작아질 때까지 최대값을 정답에 갱신
        else if(cnt>=n) {
            l=m+1;
            ans=max(ans,m);
        }
    }

    cout << ans << endl;

}