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

풀이

#include <bits/stdc++.h>
#define ll long long

using namespace std;

// 이미 가지고 있는 랜선
ll L[10001];

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

    int K,N;
    cin >> K >> N;
    // 가지고 있는 랜선 중 가장 큰 것 (모든 경우 고려하기 위해)
    ll maxi = INT_MIN;
    for (int i=0; i<K; i++) {
        cin >> L[i];
        maxi = max(maxi, L[i]);
    }
    ll st=1;
    ll en=maxi;
    ll ans;

    // 이진탐색
    while (st <= en) {
        ll mid = (st+en)/2;
        ll cnt=0;
        cout << st << ' ' << mid << ' ' << en << '\n';
        // 모든 랜선에 대해 만들 수 있는 개수합
        for (int i=0; i<K; i++) {
            cnt += L[i]/mid;
        }
        if (cnt >= N) {
            st = mid+1;
            ans = mid;
        }
        else en = mid-1;
    }
    cout << ans;
    return 0;
}

풀이

예제에 대한 전개도

이진탐색은 st와 en을 정하고, mid로 절반씩 나누며 O(logN)에 정렬된 수를 탐색하는 알고리즘이다.

 

1. 탐색할 위치를 정한다. (모든 경우 고려하기 위해, 가장 큰 랜선의 길이로)
2. mid 기준으로 언제 앞쪽, 뒤쪽을 탐색할지 조건을 정한다. (모든 랜선에 대해 각각 mid 나눈 값의 총합)
3. 탐색한다.

 

---

+a

• 부등호 및 크거나 같다, 언제 ans를 업데이트 할지.. → 시행착오로 찾아내야함

• long long을 쓴 이유
  • st, en ≤ INT_MAX 인데 (st+en)/2 의 연산 존재하므로 int overflow가 발생한다.