[BOJ 1654] 랜선 자르기 (C++)

랜선 자르기(Silver 3)

문제

전체 문제 보기

1654번: 랜선 자르기

 

접근법

문제에서 주어진 랜선을 몇 센티미터로 잘라야 필요한 N개의 랜선(모든 랜선은 같은 길이를 가져야 함.)을 만들면서 낭비 없이 가장 긴 랜선을 만들 수 있는지 묻고 있습니다. 그런데 문제는 랜선의 길이가 너무 크다는 점입니다. 랜선의 길이는 \(2^{31}-1 = 2,147,483,647\) 이기 때문에 모든 경우를 완전 탐색을 하기에는 시간이 너무나 오래 걸립니다. 그래서 이분 탐색으로 문제를 해결해야 합니다. 이분 탐색은 전체 구간을 계속 반으로 나눠서 탐색하기 때문에 \(O(\mbox{log}n)\) 시간 복잡도를 가집니다. 따라서 \(2^{31}-1\)와 같이 큰 숫자도 31회 탐색이면 정답을 구할 수 있습니다.

 

이분 탐색은 임의의 한 수를 뽑아서 답이 될 수 있는지 없는지 유효성 검사를 진행합니다. 임의의 값의 유효성 검사를 진행한 후 정답보다 값이 작다면 더 큰 수를 , 정답 보다 값이 크다면 더 작은 수를 탐색합니다. 이분 탐색 코드를 작성할 때 가장 헷갈리는 부분은 탐색 종료 조건 설정 및 탐색 범위 (left, right, mid) 값 설정입니다. 문제를 잘 읽고 탐색 범위를 명확하게 정의내리지 않으면 무한 루프에 빠지거나 원하지 않은 값을 얻게 됩니다. 보통 이분 탐색에서는 사용 가능한 값들 중 가장 큰 값, 혹은 가장 작은 값을 요구합니다. 이번 문제 같은 경우 K 개의 랜선을 잘라서 N개 이상을 만드는 것이 목표입니다. 만약 아래와 같이 4개의 랜선 이 있다고 가정합니다.

100, 150, 160, 170

 

이 4개의 랜선으로 5개 이상의 랜선을 만들고자 한다면, 모든 랜선을 10으로 자르더라도 5개 이상의 랜선에 해당하기 때문에 10은 유효한 값입니다. 그런데 만약 모든 랜선의 길이를 100으로 맞춘다면 랜선을 4개밖에 만들지 못하기 때문에 유효한 값이 될 수 없습니다. 우리는 유효한 값들 중 최대 값을 구하는 것이 목표입니다. 따라서 우선 아래와 같이 유효성을 검사할 함수를 만들 수 있습니다.

// N개의 이상의 랜선을 만들었면 true 반환
bool Check(vector<int>& arr, int N, int divisor)
{
    int cnt{};
    for (int len : arr)
    {
        cnt += len / divisor;
    }

    return N <= cnt;
}

어떤 값이 true를 반환 받았다면 다음 범위를 지정할 때 그 값을 포함해서 새로운 범위를 지정해야 할 것입니다. 왜냐면 그 값도 최댓값이 될 후보이기 때문입니다. 만약 그 값을 포함시키지 않는다면, 최댓값이 될지도 모를 수를 포기하는 샘입니다. 그리고 false를 반환 받았다면 그 수를 제외한 범위로 탐색을 이어나가면 되겠습니다. 그 값은 어처피 N개의 랜선을 만들지 못하기 때문에 정답이 될 수 없는 수이기 때문이죠. 따라서 이분 탐색 시 left와 right, mid 를 다음과 같이 설정할 수 있습니다.

int mid;
// left 와 right가 만나면 탐색 종료
while (left < right)
{
    mid = (left + 1U + right) / 2;

    if (Check(arr,mid,N)) left = mid; // true를 반환받으면 방금 탐색한 값을 포함하여 새 탐색범위 설정
    else right = mid - 1; // flase를 반환받으면 방금 탐색한 값을 제외하여 새 탐색범위 설정
}

mid = (left + 1U + right) / 2;
cout << mid << endl;

그리고 이문제는 가장 큰 랜선의 길이는 \(2^{31}-1\)이기 때문에 int 타입을 사용하는 left, right는 오버플로가 발생할 수 있습니다. 다행이 unisgined int를 넘기지 않는 범위이기 때문에 mid 값을 구하기 위해 (left + 1 + right) / 2 하는 과정에서 1을 unisgined int로 사용하여 unisgined int로 자동 형변환을 시켰습니다. 이제 아래에서 전체 소스코드를 살펴보고 이 알고리즘의 성능에 대해 다루겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
bool Check(vector<int>& arr, int divisor, int N)
{
    int cnt{};
    for (int len : arr)
    {
        cnt += len / divisor;
    }

    return N <= cnt;
}
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int K, N; //K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하 /  K ≦ N
    // 랜선의 길이는 2^31-1보다 작거나 같은 자연수

    cin >> K >> N;
    vector<int> arr(K);

    int left{ 1 }, right{ };
    for (int i = 0; i < K; i++)
    {
        cin >> arr[i];
        right = max(right, arr[i]);
    }

    int mid;

    while (left < right)
    {
        mid = (left + 1U + right) / 2;
        if (Check(arr,mid,N)) left = mid;
        else right = mid - 1;
    }

    mid = (left + 1U + right) / 2;
    cout << mid << endl;
    return 0;
}

성능 평가

이 알고리즘에서 유효성 검사를 진행하는 Check 함수는 전체 랜선을 선형 탐색합니다. 따라서 Check함수의 시간 복잡도는 \(O(N)\)입니다. 그리 while문은 1부터 최대 랜선의 길이 사이를 이분 탐색합니다. 그래서 최대 랜선의 길이를 \(L\)이라고 했을 때 총 \(O(\mbox{log}L)\)번의 반복문이 시행됩니다. 그리고 한번 반복할 때마다 시간 복잡도가 \(O(N)\) Check 함수를 한번 씩 호출합니다. 따라서 전체 시간 복잡도는 \(O(N\mbox{log}L)\) 입니다.