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

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

1654번: 랜선 자르기

이번 포스트에서는 백준 알고리즘 문제인 랜선 자르기를 포스트 하겠습니다.

 

해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다.

 

먼저 문제입니다.

입력으로 K개의 랜선 개수와 만들고 싶은 랜선의 개수 N이 주어지고, K개의 랜선의 길이가 각각 입력으로 주어집니다.

 

이때, N개를 만들 수 있는 랜선의 최대 길이를 출력하는 문제입니다.

 

해당 문제는 이분 탐색을 응용하는 parametric search 문제입니다.

 

기존의 이분 탐색은 어떠한 값을 찾기 위해 인덱스 값을 반으로 나누며 값이 위치한 인덱스를 찾는 탐색이었습니다.

 

해당 문제는 출력으로 N개의 랜선을 만들었을 때, 최대 길이를 찾는 문제로 인덱스 대신 길이를 탐색해야합니다.

 

따라서 mid값 또한 인덱스 값이 아닌 길이의 중간값이 됩니다. 따라서, 가장 긴 랜선 길이에서 2를 나누어 줍니다. (탐색범위의 최소값과 최대값이므로 가장 긴 길이의 랜선 길이로 수행)

 

그리고 해당 mid 값으로 랜선들을 나누었을 때, N개의 랜선이 나오는지를 검사하고 N개의 랜선보다 많이 나올 경우, 더 긴 길이로 잘라보는 시도를 하고, N개의 랜선보다 적게 나오는 경우, 더 짧은 길이로 잘라보는 시도를 하는 방식으로 구현합니다.

 

위 과정을 반복하면 범위가 제일 좁혀졌을 때 mid 값이 가능한 가장 긴 길이로 계산됩니다. (N개가 나올 때도 더 긴 길이로 잘라보는 시도를 하기 때문)

 

먼저 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
bool isPos(int* arr, int n, long long int mid, int tar)
{
    int tmp = 0;
    for(int i = 0; i < n; i++)
        tmp += arr[i] / mid;
 
    return (tmp >= tar);
}
 
long long int binarySearch(int* arr, int n, int last, int tar)
{
    long long int mid;
    long long int left = 1, right = last;
 
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(isPos(arr,n,mid,tar))
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left - 1;
}
 
int main()
{
    int n,k,max = 0;
    cin >> n >> k;
 
    int lan[n];
 
    for(int i = 0; i < n; ++i)
    {
        cin >> lan[i];
        max = (lan[i] > max) ? lan[i] : max;
    }
 
    cout << binarySearch(lan,n,max,k);
 
    return 0;
}

 

다음은 Python 코드입니다.

 

def isPos(arr, n, mid, tar) :
    tmp = 0
    for i in range(n) :
        tmp += arr[i] // mid
    return (tmp >= tar)
 
def binarySearch(arr, n, end, tar) :
    left = 1
    right = end
 
    while left <= right :
        mid = (left + right) // 2
        if isPos(arr,n,mid,tar) :
            left = mid + 1
        else :
            right = mid - 1
    return left - 1
 
k, n = map(int, input().split())
 
max = 0
arr = []
 
for i in range(n) :
    tmp = int(input())
    if max < tmp :
        max = tmp
    arr.append(tmp)
 
print(binarySearch(arr,k,max,n))

해당 문제는 이분탐색을 응용해야하는 문제로, 기존의 해당 값에 일치하는 값만 찾던 이분 탐색과 달리 N의 랜선을 만들 수 있음에도 계속해서 진행하여 길이의 상한을 찾아내야하는 문제입니다. 따라서, 이분 탐색의 조건식이 바뀌게 되는데 이를 빠르게 찾아내는게 중요한 문제라고 생각됩니다.

 

또한, 해당 문제에서는 정렬이 필요없는 문제로 필자는 자연스럽게 이분 탐색이니까 정렬해야겠지 ? 하면서 사용했었는데 어차피 모든 랜선의 길이가 담긴 배열을 접근하여 mid 값으로 나누기 때문에 정렬과는 연관이 없는 문제입니다. 굳이 정렬을 사용해서 시간복잡도를 낭비하는일이 없었으면 합니다.

 

다음 포스트에서도 백준 알고리즘 문제로 포스트하도록 하겠습니다. 감사합니다.