백준 온라인 저지(Baekjoon Online Judge) - 2805 : 나무 자르기

 

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

2805번: 나무 자르기

 

#include <iostream>
#include <algorithm>
using namespace std;

long BinarySearch(long* trees, long numberOfTrees, long targetLength) {
    long availableMinHeight = 0;
    long availableMaxHeight = trees[numberOfTrees - 1];
    long result = 0;

    while (availableMinHeight <= availableMaxHeight) {
        long cuttingMachineHeight = (availableMinHeight + availableMaxHeight) / 2;
        long currentTotalLength = 0;

        for (long i = 0; i < numberOfTrees; i++) {
            if (trees[i] > cuttingMachineHeight) {
                currentTotalLength += trees[i] - cuttingMachineHeight;
            }
        }

        if (currentTotalLength >= targetLength) {
            availableMinHeight = cuttingMachineHeight + 1;
            result = cuttingMachineHeight;
        }
        else {
            availableMaxHeight = cuttingMachineHeight - 1;
        }
    }

    return result;
}

int main() {
    long numberOfTrees, targetLength;
    cin >> numberOfTrees >> targetLength;

    long* trees = new long[numberOfTrees];

    for (long i = 0; i < numberOfTrees; i++) {
        cin >> trees[i];
    }

    sort(trees, trees + numberOfTrees);

    long result = BinarySearch(trees, numberOfTrees, targetLength);
    cout << result << endl;

    delete[] trees;

    return 0;
}

 

이 코드는 주어진 나무의 높이와 상근이가 가져가려는 나무의 길이(targetLength)를 입력받아 이분 탐색을 사용하여 절단기의 높이를 결정하는 프로그램입니다. 코드의 주요 구성 요소를 설명하겠습니다.

1. BinarySearch 함수:
- BinarySearch 함수는 이분 탐색을 수행하여 절단기의 높이를 결정하는 역할을 합니다.
- 함수는 주어진 나무의 배열(trees), 나무의 개수(numberOfTrees), 그리고 상근이가 가져가려는 나무의 길이(targetLength)를 매개변수로 받습니다.
- 함수 내부에서는 이분 탐색을 사용하여 절단기의 높이를 조정합니다.
- 이분 탐색은 현재 가능한 절단기의 최소 높이(availableMinHeight)와 최대 높이(availableMaxHeight)를 가지고 탐색 범위를 좁혀가며 반복적으로 수행됩니다.
- 각 반복에서는 현재의 절단기 높이(cuttingMachineHeight)를 계산하고, 해당 높이로 잘린 나무의 길이를 계산합니다.
잘린 나무의 길이가 상근이가 가져가려는 나무의 길이(targetLength)보다 크거나 같으면, 절단기의 높이를 높여서 더 많은 나무를 가져갈 수 있도록 탐색 범위를 조정합니다.
- 그렇지 않은 경우에는 절단기의 높이를 낮춰서 더 적은 양의 나무를 가져갈 수 있도록 탐색 범위를 조정합니다.
- 이분 탐색이 끝난 후에는 최종 결정된 절단기의 높이(result)를 반환합니다.

 

2. main 함수:

- main 함수는 프로그램의 진입점으로, 주요 실행 흐름을 담당합니다.
- 먼저, 나무의 개수(numberOfTrees)와 상근이가 가져가려는 나무의 길이(targetLength)를 입력받습니다.
- 그 다음, 나무의 높이를 저장할 배열인 trees를 동적으로 할당합니다.
- numberOfTrees만큼 반복하면서 각 나무의 높이를 입력받습니다.
- 이후, std::sort 함수를 사용하여 trees 배열을 오름차순으로 정렬합니다.
- 정렬된 배열과 입력받은 targetLength를 BinarySearch 함수에 전달하여 절단기의 높이를 결정합니다.
- 결정된 절단기의 높이를 result 변수에 저장합니다. 그리고 result 값을 출력하여 절단기의 높이를 사용자에게 보여줍니다.
- 마지막으로, 동적으로 할당된 trees 배열을 해제하여 메모리 누수를 방지합니다. 그리고 0을 반환하여 main 함수의 종료를 나타냅니다.
- 이렇게 main 함수는 입력받은 데이터를 처리하고 이분 탐색을 통해 최적의 절단기 높이를 결정하는 역할을 수행합니다.

 

* 해당 게시물은 ChatGPT를 참고하여 작성되었음을 알립니다.