[Baekjoon] [1654 : 랜선자르기] 이진탐색과 문제풀이

문제 설명

---

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

1654번: 랜선 자르기

 

지난 인증시험 이후 충격을 많이 받았기에 차근차근 코딩 문제도 풀어보려고 합니다.

 

solved ac에서 티어를 올릴 생각으로 차근차근 푸는데, 이번 문제는 이진탐색을 사용하지 않으면 시간초과가 뜨는 문제였습니다.

 

입력받을 선의 갯수를 말하고, 원하는 갯수가 들어오면 그 갯수를 만들 수 있는

최대로 자르는 길이를 출력하는 문제인데

 

갯수가 몇 개인지는 그냥 입력받은 몫끼리 더하면 되고

 

나누는 수를 탐색을 통해 찾아야 했답니다.

 

이진탐색

---

이진탐색(binary search)는 정렬되어 있는 배열에서 특정한 값을 찾는 알고리즘으로

O(log N)의 시간복잡도를 가집니다.

 

정렬 되어있어야 합니다!

 

근데 저희가 풀 문제에선 자연수는 어차피 정렬된 상태이니 별로 신경쓰지 않아도 되겠습니다.

 

 

탐색 과정은 다음과 같습니다.

0. 정렬한다. (오름차순일 때로 설명)

1. 중간값을 잡는다.

2. 중간값과 검색값을 비교한다.

3. 검색값이 중간값보다 크면 중간값 기준 오른쪽 배열을 검사한다.

4. 중간값보다 작으면 중간값 기분 왼쪽 배열을 검사한다.

5. 중간값이 검색 결과와 같으면 종료한다. 

 

중고등학교 정보시간에도 배우긴 하는데,

그림으로 나타내면 이렇게 됩니다.

이렇게 되면 중앙값만 검사해서 원하는 숫자를 빠르게 찾을 수 있습니다.

 

여기서 오른쪽, 왼쪽을 검사하기 위해서 low, high, mid 변수를 선언합니다.

 

 

풀이

---

이번 문제에서는 나누는 숫자가 크면 원하는 랜선 갯수보다 작게 나오고

나누는 숫자가 작으면 원하는 랜선 갯수보다 큽니다.

 

처음 high는 입력받은 값의 max로 잡으면 되고

low는 1로 잡으면 구간을 잡을 수 있습니다.

 

만약 만들어진 전선 갯수가 원하는 갯수(n)보다 작으면 숫자가 큰 것이므로 왼쪽을 탐색합니다(high = mid-1)

만들어진 전선 수가 n보다 크거나 같으면 low에 mid+1을 대입합니다.

 

여기서 중요했던 부분이 종료조건인데.

 

문제 조건에서

 N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

이렇게 말했으니 같을 때에도 오른쪽을 탐색하도록 최대한 mid 값을 키워가면서 mid가 최대일 때가 답이 됩니다.

 

 

음...

 

그래서 코드는 

 

#include<stdio.h>

int make_lan(int *, unsigned int, int);

int main(void)
{
    int k, n;
    int length[10000];
    int max = -1;
    int made_num;   
    int res;
    
    unsigned int high, low, mid;

    scanf("%d %d",&k, &n);

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

    high = max;
    low = 1;
    res = 1;

    while(low <= high)
    {
        mid = (low+high)/2;
        made_num = make_lan(length, mid, k);

        if(made_num >= n)
        {
            low = mid+1;
            if(res < mid)
            {
                res = mid;
            }
        }
        else if(made_num < n)
        {
            high = mid-1;
        }
    }
    
    printf("%d", res);

    return 0;

}

int make_lan(int *length, unsigned int max_len, int k)
{
    int make_cnt=0;
    for(int i=0; i<k; i++)
    {
        make_cnt += length[i]/max_len;
    }

    return make_cnt;
}

 

이렇긴 한데, 손으로 어떻게 계산되어가는지 해보는게 좋을 거 같네요.

 

작은 수 중에서도 최대를 골라야한다는