[백준 C++] 2805 나무 자르기 - 이분탐색

2805번: 나무 자르기

cpp

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

int main()
{
‌int N, M;
‌cin >> N >> M;

‌vector<int> Trees;
‌Trees.reserve(N);
‌for (int i = 0; i < N; ++i)
‌{
‌‌int Tree;
‌‌cin >> Tree;
‌‌Trees.emplace_back(Tree);
‌}

‌int Result = 0;
‌int Height = 0;
‌int MinHeight = 0;
‌int MaxHeight = *max_element(Trees.begin(), Trees.end());
‌while (MinHeight <= MaxHeight)
‌{
‌‌Height = (MinHeight + MaxHeight) / 2;

‌‌long long Sum = 0;
‌‌for (const int& Tree : Trees)
‌‌{
‌‌‌if (Tree > Height)
‌‌‌{
‌‌‌‌Sum += Tree - Height;
‌‌‌}
‌‌}

‌‌if (Sum < M)
‌‌{
‌‌‌MaxHeight = Height - 1;
‌‌}
‌‌else
‌‌{
‌‌‌Result = Height;
‌‌‌MinHeight = Height + 1;
‌‌}
‌}

‌cout << Result;
}

---

 

높이의 범위를 좁혀가며 이분 탐색하도록 할 때

조건을 어떻게 잡느냐에 따라서

시간초과 발생 유무가 있습니다.

 

그리고 M의 범위가 (1 ≤ M ≤ 2,000,000,000)이므로

Sum의 자료형 선택에도 주의가 필요합니다.