[BOJ] 2805 : 나무 자르기 (C++)

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

2805번: 나무 자르기

걸린 시간 : 25분 2초

---

몇몇 Parametric Search 문제를 봤지만, 항상 어떤 알고리즘을 써야 할지 몰랐다. 하지만 이번 문제는 단번에 Parametric Search인 것을 알았다. 이 문제를 참고하자 자세한 매개 변수 탐색에 관한 이야기를 적어놨다. https://morenow.tistory.com/44

[BOJ] 2110 : 공유기 설치 (C++)

핵심은 개방형 질문, 즉 "어떤 높이로 나무를 자르는 게 최댓값일까?" 가 어렵다면, "이 높이로 나무를 자르는 게 최댓값일까?" 라는 질문을 N 번 수행하자는 의미이다.

이진 탐색을 N번 수행하므로 시간 복잡도는 O(NlogN) 이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> tree;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		tree.push_back(tmp);
	}
	int st = 0, en = 0, answer = 0;
	for (int i = 0; i < N; i++) {
		en = max(en, tree[i]);
	}
	
	while (st <= en) {
		int mid = (st + en) / 2;
		long long total = 0;
		for (int i = 0; i < N; i++) {
			if (tree[i] > mid) total += tree[i] - mid;
		}
		if (total < M) {
			en = mid - 1;
		}
		else {
			answer = mid;
			st = mid + 1;
		}
	}
	cout << answer;
	return 0;
}