백준 C++ 2805번) 나무 자르기

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

2805번: 나무 자르기

 

풀이)

 

어제 풀었던 문제와 같이, 매개 변수 탐색 알고리즘을 사용해야 한다. 트리 길이를 입력받을 때 제일 큰 값을 end의 값으로 설정해두고, start를 0으로 설정한다. 그리고 구한 start와 end 값으로 이분탐색을 해 나가면서 최댓값을 찾아내면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long int64;

int main() {
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	
	int N, M;
	int64 input;
	vector<int64> tree;

	cin >> N >> M;
	int64 max = 0;
	for (int i = 0; i < N; i++) {
		cin >> input;
		tree.push_back(input);
		if (max < input)
			max = input;
	}

	int64 start = 0;
	int64 end = max + 1;
	while (start + 1 < end) {
		int64 mid = (start + end) / 2;
		int64 n = 0;
		int64 total = 0;
		for (int64 i = 0; i < N; i++) {
			n = tree[i] - mid;
			if (n > 0)
				total += n;
		}
		if (total < M)
			end = mid;
		else
			start = mid;
	}
	cout << start << "\n";
}