[C] 백준 | 2805번 코드 - 나무 자르기

>문제

> 핵심

이분탐색

long long형

>풀이과정

이 문제,, 어딘가 낯이 익다 했더니

1654번 문제 "랜선 자르기" 랑 구조가 거의 똑같다!!

 

그래서 나무의 최대 길이가 2,000,000,000이라는 점에서 int형이 아니라 long long 형을 사용해야 한다는 점을 잊지 않고 사용해서 어렵지 않게 문제를 풀 수 있었다.

 

우선 나무의 길이를 입력받으면서 가장 긴 나무의 길이를 max에 저장한다.

그리고 이분탐색을 위해 left = 0, right = max

 

(left <= right)인 동안

mid = (left + right) / 2    (<- mid : 절단기의 높이)

로 나무들을 잘랐을때 길이가 얼마나 남는지를 sum 하고 길이가 못미치면 right = mid-1, 길이가 남으면 left = mid+1

 

여기서 길이가 남는경우(sum > m), 현재 절단기의 높이를 비교해 큰값을 cut_max변수에 저장해두는걸 잊으면 안된다!!!

글로 쓰니까 뭔소리를 하는지 정리가 안된다. 역시 글쓰는건 어렵다.

>깨달은점

한번 풀어본 유형은 어떻게 풀어야겠다는 감이 빨리 온다는걸 이 문제로 느꼈다.

클래스 2는 이제 거의 다 풀어가는데 앞으로도 계속 다양한 유형의 문제를 접해봐야겠다.

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m, i;
    int* tree_list;
    long long left, mid, right, sum, max, cut_max;

    scanf("%d %d", &n, &m);
    tree_list = (int*)malloc(n * sizeof(int));

    for (i = 0, max = 0; i < n; i++)
    {
        scanf(" %d", &tree_list[i]);

        // 나무 중 제일 긴 나무의 길이 저장.
        if (max < tree_list[i])
        {
            max = tree_list[i];
        }
    }

    left = 1, right = max, cut_max = 0;
    while (left <= right)
    {
        // 절단기 높이.
        mid = (left + right) / 2;

        for (i = 0, sum = 0; i < n; i++)
        {
            // 절단기 높이보다 긴 나무의 경우에만 sum.
            if (tree_list[i] - mid > 0)
            {
                sum = sum + (tree_list[i] - mid);
            }
        }

        // 원하는 길이에 못미치므로 절단기 높이를 낮춰야함
        if (sum < m)
        {
            right = mid - 1;
        }
        // 절단기 높이를 더 높여도 됨.
        else
        {
            //절단기의 최대높이 갱신
            if (cut_max < mid)
            {
                cut_max = mid;
            }
            left = mid + 1;
        }
    }

    printf("%lld\n", cut_max);

    free(tree_list);
    return 0;
}