[백준] 1654번: 랜선 자르기 (C++)

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

1을 start로, 랜선 K개중에서 가장 큰 값을 end로 지정하여 이분 탐색을 진행하면 해결 가능합니다.

조건을 만족하는 mid 값을 찾았을때 break 하고 출력을 했는데, 계속 '틀렸습니다'가 떠서 당황스러웠습니다.

 

 

실패 소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k, n, mx;
ll arr[10000];

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

    cin >> k >> n;
    for (int i = 0; i < k; i++)
        cin >> arr[i];
    sort(arr, arr + k);

    ll s = 1, e = arr[k - 1];
    ll mid;
    while (s <= e) {
        ll sum = 0;
        mid = (s + e) / 2;
        
        for (int i = 0; i < k; i++)
            sum += arr[i] / mid;
        
        if (sum == n) break;
        else if (sum < n) e = mid - 1;
        else s = mid + 1;
    }
    cout << mid;

    return 0;
}

mid 값으로 각각 랜선길이를 나눠서 더해준 sum 값이 N과 같으면 break를 해주고 mid를 출력한 경우입니다.

물론 위에서 mid 값이 최대 길이가 될 수 있지만, mid보다 더 큰 값이 될 수 있는 경우도 있습니다.

그렇기 때문에 sum == n를 만족한다고 mid가 답이 될 수 없습니다.

 

 

성공 소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll k, n, mx;
ll arr[10000];

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

    cin >> k >> n;
    for (int i = 0; i < k; i++)
        cin >> arr[i];
    sort(arr, arr + k);

    ll s = 1, e = arr[k - 1];
    ll mid;
    while (s <= e) {
        ll sum = 0;
        mid = (s + e) / 2;
        
        for (int i = 0; i < k; i++)
            sum += arr[i] / mid;
        
        if (sum >= n) s = mid + 1;
        else e = mid - 1;
    }
    cout << e;

    return 0;
}