[Algorithm]Baekjoon 1654번 :: 랜선 자르기

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

1654번: 랜선 자르기

 
 
using namespace std;
 
int k, n;
long long arr[10001];
 
bool check(long long mid)
{
    long long result = 0;
 
    for (int i = 0; i < k; ++i)
    {
        result += arr[i] / mid;
    }
 
    if (result >= n) return true;
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> k >> n;
 
    for (int i = 0; i < k; ++i)
    {
        cin >> arr[i];
    }
 
    long long left = 1;
    long long right = pow(2, 31) - 1;
    long long answer = 0;
 
    while (left <= right)
    {
        long long mid = (left + right) / 2;
        
        if (check(mid))
        {
            left = mid + 1;
            answer = max(answer, mid);
        }
        else
        {
            right = mid - 1;
        }
    }
 
    cout << answer;
}
 
 

 

너무 dp문제만 푸는것같아서 오랜만에 이분탐색관련된 문제를 풀어봤다.

정답비율이 낮은 문제긴 했지만, 예전에 문제풀때 꽤 꼼꼼히 풀었어서 그런가, 쉽게 풀 수 있었다.

 

사실 엄청 어렵게 낸거 아니면, 이분탐색문제는 눈치채기가 의외로 좀 쉽다.

이번문제같은경우는 k개만큼의 랜선이 주어졌을 때, 주어진 n개 만큼의 똑같은 길이의 랜선들을 만들어야 한다.

문제에서는 최대 랜선길이를 구하는거라서 무작정 탐색으로 풀려하면 당연~히 시간복잡도에 걸린다.

 

그러니 애초에 그냥 랜선길이를 기준으로 잡고, 해당 랜선길이로 잘랐을 시 n개를 만족하는지를 체크하면서 이분탐색을 진행하면 된다.

랜선 최대길이는 21억4천7백만쯤 되기때문에 시간복잡도에 걸릴 것 같지만, 이분탐색으로 범위를 좁혀나가면서 절반씩 자르면서 탐색하기때문에 30몇번밖에 탐색 안한다.

그렇게 mid값을 찾을 때마다 k번만큼의 반복문을 수행하니, 결국 log2^31-1 * k 정도의 시간복잡도다.

log2^31-1을 대략 31이라잡고, k는 최대값이 1만이니 시간복잡도는 31만정도로 계산할 수 있다.

 

각 check마다 몫을 나눠서 누적한값이 n이상일 경우, 즉 더 개수가 목표치 이상일 경우 자르는 길이를 더 길게 잘라도 되는 여유가 있다는 것이니 범위를 늘린다. 

하지만 n 미만일 경우 더 짧게잘라서 개수를 늘려줘야하니 범위를 줄여주는것이다.