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

해당 문제는 2진 탐색 알고리즘으로 풀 수 있다.

입력

반응형

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

입력에선 랜선의 개수 K, 필요한 랜선의 개수 N, K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이를 받아야 한다.
이 때, 중요한 것은 2의31승 - 1 즉 21억 int의 최대값을 의미한다. 이는 K가 10,000이 입력되고
각 줄 마다 랜선에서 int의 최대값 ( 약 21억 ) 을 모두 더하면, 랜선의 총 길이는 21,476,983,953,647가 된다.
랜선의 총 덧셈한 이유는 차후 설명하겠다. 일단 알아만 두자

입력코드

#define MAX 10'001

int K, N;
int LanCable[MAX];
int HighLenght = 1;
void Input()
{
    cin >> K >> N;
    for (int i = 0; i < K; i++)
    {
        cin >> LanCable[i];
        if (LanCable[i] > HighLenght)
            HighLenght = LanCable[i];
    }
}

입력 코드를 살펴보자 K,N을 일단 받아두고, LanCable은 K가 받을 수 있는 최대 입력값 + 1을 해준다.
HightLenght를 보면, LanCable을 입력 받을 때 마다 크기를 비교해준 후 넣어주고 있는데. 
이유에 대해선 2가지로 나뉜다.
1. 우리는 최대 랜선의 값을 알아야 한다.
- 예시 입력으로 802,457,743,539 가 주어질 때, 802 이상으로 나눌 수 있는게 없기 때문이다.

2. 정렬 알고리즘을 사용시 오버헤드가 발생한다.
-> 최대값을 알아낸 후, 정렬을 돌리면 그에 따른 오버헤드가 발생하기 때문에 입력을 받을 때 마다 비교하는 것이.
더 빠르다.

풀이코드

int64 HighMid = 0;
void Solution(int64 low, int64 high)
{
    if (low > high) return;

    int64 mid = (low + high) / 2;
    int64 sumCable = 0;
    for (int64 i = 0; i < K; i++)
    {
        sumCable += LanCable[i] / mid;
    }

    if (sumCable >= N)
    {
        HighMid = max(HighMid, mid);
        Solution(mid + 1, high);
    }
    else {
        Solution(low, mid - 1);
    }
}

void Solve()
{
    Input();
    Solution(1,HighLenght);
    cout << HighMid << endl;

}

최초로 최대 길이를 High로 넣어주고 N의 최소값 1을 넣어서 재귀로 이진탐색을 진행한다.
이 때 SumCable을 LanCable마다 mid로 나눠준다.
예를들어  어떠한 Lancable이 802라고 한다면. 802/401은 2개가 나온다.
하지만 앞서 언급한 Lancable의 길이는 21억 까지 나올 수 있고, Mid가 2가 될 수있으며, K가 10,000 이라면 int로는
모두 담을 수 없다. 하여 long long 자료형으로 담아줘야 하며 이를 int64로 바꿔놨다. 추후 사용법은 전체코드를
보면 알 수 있다. 

여하튼 이렇게 모두 더한 SumCable의 개수가 N과 같거나 높을 때 HighMid에 담아주고, max 함수를 사용하여 현재
mid와 Highmid를 비교한 후 더 큰 값을 넣어주었다.
간단히, 더 큰 길이를 저장한다고 보면 된다.

이후, low 값을 좁힌 뒤, 다시 재귀를 돌리고 
만약 N보다 SumCable 개수보다 적다면, High 값을 좁혀준다.

전체코드

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

#define MAX 10'001

using int64 = __int64;

int K, N;
int LanCable[MAX];
// 가장 큰 값을 2분탐색 때 High로 넣기 위함.
int HighLenght = 1;
void Input()
{
    cin >> K >> N;
    for (int i = 0; i < K; i++)
    {
        cin >> LanCable[i];
        if (LanCable[i] > HighLenght)
            HighLenght = LanCable[i];
    }
}

int64 HighMid = 0;
void Solution(int64 low, int64 high)
{
    if (low > high) return;

    int64 mid = (low + high) / 2;
    int64 sumCable = 0;
    for (int64 i = 0; i < K; i++)
    {
        sumCable += LanCable[i] / mid;
    }

    if (sumCable >= N)
    {
        HighMid = max(HighMid, mid);
        Solution(mid + 1, high);
    }
    else {
        Solution(low, mid - 1);
    }
}

void Solve()
{
    Input();
    Solution(1,HighLenght);
    cout << HighMid << endl;

}

int main()
{
    Solve();
}