백준_1654_랜선자르기

 

 

 

랜선의 개수와 필요한 랜선의 개수가 주어졌을 때 

그 개수만큼 만들 수 있는 랜선의 최대 길이를 구하는 문제입니다.

 

 

초기 코드)

#include <stdio.h>

void lan_cal(int lan_length[], int max, int lan_count, int lan_need);

int main(void)
{
    int lan_count = 0, lan_need = 0;
    scanf("%d %d", &lan_count, &lan_need);

    int lan_length[lan_count];

    int max = 0;
    for (int i = 0; i < lan_count; i++)
    {
        scanf("%d", &lan_length[i]);
        if (lan_length[i] > max)
            max = lan_length[i];
    }

    lan_cal(lan_length, max, lan_count, lan_need);

    return 0;
}

void lan_cal(int lan_length[], int max, int lan_count, int lan_need)
{
    int result = 0;

    for (int i = max; i > 0; i--)
    {
        int temp = 0, sum = 0;
        for (int j = 0; j < lan_count; j++)
        {
            temp = lan_length[j] / i;
            sum += temp;
        }
        if (sum == lan_need)
        {
            result = i;
            break;
        }
    }
    printf("%d\n", result);
}

 

랜선의 길이들을 배열에 넣은 뒤, 하나하나 계산해가며 결과를 구하는 방식입니다.

 

하지만, 미처 생각하지 못한 점이 있었습니다.

 

바로 랜선의 길이가 2^31 - 1 보다 작거나 같은 자연수라는 점입니다.

 

최악의 경우, 2^31 - 1 번 반복해야 할 수도 있으니 당연히 시간 초과가 날수밖에 없겠죠.

 

그렇다면, 방대한 크기의 데이터가 주어졌을 때, 최악의 경우에도 시간 효율이 좋은 방식이 뭐가 있을까 생각을 해보아야겠죠.

 

 

이 문제에서는, 이분 탐색을 이용하는 것이 좋아보입니다.

 

이분 탐색은, 탐색해야하는 구간을 절반씩 줄여가며 탐색해나가는 과정이기 때문에,

 

최악의 경우이더라도 연산 횟수가 많지 않습니다.

 

https://www.acmicpc.net/blog/view/109

 

 

이 사이트에서 이분 탐색에 대해 정말 잘 설명해주고 있습니다.

 

주의해야할 점과 작동 방식 등이 잘 기제되어있으니 한번 보고 오시는 것을 추천드립니다.

(백준 문제를 푸시는 분이라면 확실히 도움이 될 것입니다.)

 

 

문제 코드)

#include <stdio.h>

int binary_search(long long lan_length[], int size, long long left, long long right, int lan_need);

int main(void)
{
    int lan_count = 0, lan_need = 0;
    scanf("%d %d", &lan_count, &lan_need);

    long long lan_length[lan_count];
    int size = lan_count;

    long long max = 0;
    for (int i = 0; i < lan_count; i++)
    {
        scanf("%lld", &lan_length[i]);
        if (lan_length[i] > max)
            max = lan_length[i];
    }
    long long left = 0, right = max;
    binary_search(lan_length, size, left, right, lan_need);
    return 0;
}

int binary_search(long long lan_length[], int size, long long left, long long right, int lan_need)
{
    if (lan_need == 1)
    {
        printf("%lld\n", right);
        return 0;
    }

    int check = 0;
    if (size >= 2)
    {
        for (int i = 0; i < size - 1; i++)
        {
            if (lan_length[i] == lan_length[i + 1])
            {
                check++;
            }
        }
        if (check == size - 1)
        {
            printf("%lld\n", lan_length[0]);
            return 0;
        }
    }

    while (left < right)
    {
        long long mid = (left + right) / 2;

        int temp = 0;
        for (int i = 0; i < size; i++)
        {
            temp = temp + lan_length[i] / mid;
        }
        if (temp >= lan_need)
        {
            left = mid + 1;
        }
        else if (temp < lan_need)
        {
            right = mid;
        }
    }
    printf("%lld\n", left - 1);
    return 0;
}

 

 

찾으려는 값보다 작을때 , 크거나 같을 때로 경우를 나누어 탐색을 진행하였습니다.

 

크거가 같을 떄로 설정한 이유는, 가능한 값 중 가장 큰 값을 찾아야 하기 때문입니다.

 

 

 

그리고, 또 하나 신경써야 할 점은 while 문만 실행했을 때 나오는 예외들입니다.

 

첫 번째 예외로는, 필요한 랜선이 하나일 떄입니다.

랜선이 하나 필요할 때 가장 긴 랜선의 길이는 입력받은 배열에서 그냥 최댓값이겠죠.

 

두 번째 예외로는, 크기가 2 이상인 배열이 모두 같은 숫자로 이루어져 있을 떄입니다.

while 문을 실행하면 , 

K=3, N=3, 10, 10, 10 을 입력했을 떄와

K=3, N=3, 10, 10, 9 를 입력했을 때의 결과가 동일하게 나옵니다.

 

그래서, 배열이 모두 같은 수로 이루어져 있을 때를 예외처리해주었습니다.

 

 

 

이렇게 위의 두 예외들만 따로 처리해준다면, 문제에서 요구하는

이분 탐색이 정상적으로 잘 작동하는 것을 확인할 수 있습니다.