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

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

제출 코드

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

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

    int k, n, input;
    long long right, left, mid;
    vector<int> v;
    cin >> k >> n;
    while(k--)
    {
        cin >> input;
        v.push_back(input);
    }
    sort(v.begin(), v.end());

    right = v.back();
    left = 1;
    mid = (left + right) / 2;
    while(left + 1 < right)
    {
        int count = 0;
        for (auto cm : v)
            count += cm / mid;

        if (count >= n)
            left = mid;
        else
            right = mid;

        mid = (left + right) / 2;
    }

    int count = 0;
    for (auto cm : v)
        count += cm / (mid + 1);
    if (count >= n) mid++;

    cout << mid;
}

이분 탐색/매개 변수 탐색과 관련된 설명글을 참고하여 위와 같이 풀이하였다

다만 내가 아직 완전히 이해하지 못한 것인지... 

1 1

7

과 같은 반례의 경우 7까지 도달하지 못하고 6에서 while문을 탈출해버린다

그렇다고 while 문에서 left < right로 조건을 줄 경우, while 문 자체를 탈출하지 못해서 시간 초과가 뜬다

 

따라서 임시방편 느낌으로 while문 탈출 후에 1을 더한 값으로 한 번 더 계산을 시켜서 만약 1을 더한 값도 조건을 만족한다면 해당 값을 출력하고, 아니면 이전 값을 출력하도록 했더니 정답처리는 되었다

그리고 다른 사람들의 코드를 참고하여 개선점을 찾아보았다

1. 최대값을 구할 때 나는 sort를 시켜서 최대값을 찾아냈는데, 대신 입력을 받을 때마다 max 함수로 체크해주는 방식이 더 많이 보였다

2. count 값에 따라 mid의 수를 바꿔주는 과정에서 1을 더하거나 빼는 과정을 넣어줬어야 하는데, 그냥 mid를 left와 right에 넣었기 때문에 위와 같은 반례가 발생하였다

 

아래는 이를 참고하여 개선한 코드다

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

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

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

    long long right = maxLen;
    long long left = 1;
    long long mid = (left + right) / 2;

    while(left <= right)
    {
        int count = 0;
        for (auto cm : v)
            count += cm / mid;

        if (count >= n)
            left = mid + 1;
        else
            right = mid - 1;

        mid = (left + right) / 2;
    }

    cout << mid;
}

 

아래는 관련해서 보충 정리...

정답이 4일 경우로 가정

 

이런 식으로 결국 left와 right 사이의 범위를 절반으로 줄여나가는 식으로 탐색을 거쳐서, left와 right 값이 교차하게 될 때가 정답이 되는 방식이다

 

정답이 5인 경우도 마찬가지로, left와 right가 동일해지는 시점 이후에 left와 right가 교차했을 때 비로소 답이 5라고 내놓게 된다

 

결국 left와 right가 동일해지는 시점(left~right까지의 범위 내에 있는 요소가 1개일 때)에서 left가 증가해서 교차하냐, right가 감소해서 교차하냐에 따라 마지막 출력이 결정되는 것이다

 

그렇기 때문에 위에서 while loop를 돌 때의 조건이 left <= right인 것이다

만약 등호를 빼버리면 위의 정답이 4인 케이스에서는 교차하지 못하고 5를 출력하게 되기 때문이다