득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 1. 29. 10:14
 

2805번: 나무 자르기

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보

www.acmicpc.net

#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의 자료형 선택에도 주의가 필요합니다.