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

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

2805번: 나무 자르기

수행시간 : 약 50분 / 난이도 : 실버 3

 

이분탐색을 어떤식으로 응용할 수 있냐? 라는 질문에 가장 좋은 예로 들수 있는 문제라고 생각한다. 처참한 정답률은 이 문제의 난이도가 생각보다 어렵다는 것을 알 수 있게 해준다.

이 문제의 핵심 아이디어는 초기 MAX값을 나무길이의 가능한 MAX 값으로 설정, 초기 MIN 값을 1로 설정 후 이분 탐색을 통해 자를 수 있는 나무의 크기를 하나씩 줄이거나 늘리면서 찾아가는 서치 알고리즘을 구현하는 것이다. 

 

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

int n;
long long m;
vector<long long> v;

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	v.resize(n);
	for (int i = 0;i < n;++i) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
}

void sol() {
	long long max_val = 1000000000;
	long long min_val = 1;
	long long mid_val;
	long long sum = 0;
	while (min_val <= max_val) {
		mid_val = (max_val + min_val) / 2;
		sum = 0;
		for (int i = 0;i < n;++i) {
			if (v[i] >= mid_val) {
				sum += v[i] - mid_val;
			}
		}
		if (sum >= m) {
			min_val = mid_val + 1;
		}
		else if (sum < m) {
			max_val = mid_val - 1;
		}
	}
	cout << max_val;
}

int main() {
	input();
	sol();
}