[백준 2805] 나무 자르기 C++

문제

백준 2805 나무 자르기 C++

2805번: 나무 자르기

풀이

전형적인 이분 탐색 문제입니다.

low = 0, high는 나무의 최대 높이로 설정한 뒤, mid 값을 바꿔가며 이분 탐색을 시행합니다.

low > high 조건을 만족하기 전의 result 값이 최종결과가 됩니다.

sum은 int 범위를 초과할 수 있으므로 long long 타입으로 설정합니다.

 

한편, N의 최대 개수가 백만이라 시간초과가 나지 않을까 걱정했지만, C++은 N = 1억일 때 1초 정도 걸린다고 한다.

그 전에는 N = 백만일 때 1초 정도 걸리는 걸로 기억하고 있었는데, 아마 $O(n^2)$이랑 헷갈리지 않았나 싶다.

소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M;
    cin >> N >> M;
 
    vector<int> v;
    int height;
 
    int low = 1;
    int mid = 0;
    int high = 0;
    int result = 0;
 
    for (int i = 0; i < N; i++)
    {    
        cin >> height;
        v.push_back(height);
 
        if (height > high)
        {
            high = height;
        }
    }
 
    while (1)
    {
        if (low > high)
            break;
 
        mid = (low + high) / 2;
        long long sum = 0;
 
        for (int treeHeight : v)
        {
            int cutHeight = treeHeight - mid;
 
            if (cutHeight > 0)
            {
                sum += cutHeight;
            }
        }
 
        // 목표치 달성
        if (sum >= M)
        {
            result = mid;
            low = mid + 1;
        }
        // 목표치 미달성
        else
        {
            high = mid - 1;
        }
    }
 
    cout << result;
    return 0;
}