[99클럽/코딩테스트 챌린지/C++] 나무 자르기 문제에서 이분 탐색을 활용한 최적 높이 찾기

오늘은 이분 탐색을 통해 나무를 절단하는 최적의 높이를 찾는 방법을 배웠습니다. 이 문제는 주어진 나무 길이들에서 특정 높이를 설정하여 원하는 만큼의 목재를 얻을 수 있는 최대 높이를 구하는 문제였습니다. 이분 탐색을 활용하여 탐색 범위를 좁혀가면서 효율적으로 최적 값을 구할 수 있었습니다.

문제 링크 : 

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

 

문제 접근 과정

1, 문제 분석과 탐색 범위 설정

• 주어진 나무 길이 중에서 **절단기 높이 H**를 설정하여 H 이상의 부분만 자릅니다.
• H를 낮추면 더 많은 나무를 얻을 수 있지만, 우리는 필요한 양의 나무를 얻을 수 있는 최대 높이를 찾아야 하므로 탐색 범위를 점차적으로 줄이며 최적의 H를 찾습니다.
• 높이 범위는 0부터 가장 높은 나무의 높이까지 설정하여, 이분 탐색으로 중간값을 설정하고 탐색을 반복합니다.

2, 이분 탐색을 통한 최적 높이 찾기

• 중간 높이 mid를 기준으로 각 나무의 height - mid 만큼의 나무를 얻는 시뮬레이션을 합니다.
• 총 얻은 나무 길이가 필요한 길이 M 이상인 경우, mid 값을 높여 더 큰 높이에서 자를 수 있는지 확인합니다.
• 그렇지 않으면, mid 값을 낮추어 필요한 양을 얻기 위한 더 낮은 높이를 찾습니다.

3, 결과 업데이트와 최적화

• 조건을 만족할 때마다 result를 갱신하여 현재까지의 최대 절단 높이를 기록하고, 이분 탐색을 통해 반복을 최적화했습니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long N, M;
vector<int> trees;

long long srearch()
{
    long long left = 0;
    long long right = 1000000000;
    int result = 0;
    while (left <= right)
    {
        long long mid = (left + right) / 2;
        long long sum = 0;
        for(int i = 0; i < N; i++)
        {
	        if(trees[i] > mid)
	        {
                sum += trees[i] - mid;
	        }
        }
        if(sum >= M)
        {
            result = result < mid ? mid : result;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return result;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    std::cin >> N >> M;
    trees = vector<int>(N);
	for(int i = 0; i < N; i++)
    {
        std::cin >> trees[i];
    }

    sort(trees.begin(), trees.end());

    std::cout << srearch() << std::endl;
	return 0;
}

 

배운 점과 결론

이번 문제를 통해 이분 탐색을 통해 최적의 값을 찾는 방법과 탐색 범위 설정의 중요성을 배울 수 있었습니다.

 

1, 이분 탐색의 효율성

• 탐색 범위를 절반씩 줄여가며 최적 값을 찾아가는 방식이 매우 효율적이라는 것을 실감했습니다. 특히 큰 범위를 다룰 때 이분 탐색을 통해 빠르게 탐색할 수 있음을 배웠습니다.

2, 탐색 범위 설정과 초기화

• 절단기 높이를 조정하는 문제의 특성상 left와 right를 나무의 최소 높이와 최대 높이로 설정하여 범위를 좁혀가며, 불필요한 반복을 줄였습니다.

3, 조건에 맞는 결과 갱신 방식

• result 변수를 통해 현재까지의 최대 높이를 저장하고, 탐색 중 조건이 충족될 때마다 갱신하는 방식이 효율적이라는 점을 느꼈습니다. 필요한 양을 얻는 높이 중 최댓값을 구할 때 이러한 방법이 유용합니다.

결론

이번 문제를 통해 최적의 값을 구할 때 이분 탐색을 사용하는 방법과 탐색 범위 설정의 중요성을 다시 한번 깨달을 수 있었습니다. 앞으로도 최적화 문제에서 이분 탐색을 활용하여 더 효율적으로 문제를 풀어가야겠다고 느꼈습니다.