백준2805 - 나무 자르기

https://www.acmicpc.net/status?group_id=6459

채점 현황

이분탐색을 이용한 문제였다. 적어도 n만큼의 나무를 잘라서 가져가야 된다. 우선 0부터 가장 긴 나무의 길이를 자를 수 있는 길이의 범위로 설정하고 탐색을 하였다. 현재 위치에서 나무를 잘랐을 경우 n과 같거나 n보다 긴 경우는 최솟값의 범위를 줄이고 그 반대의 경우는 최댓값의 범위를 줄인다.

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

int main() {
	int m, n;
	int ans = -1;
	vector<int> v;
	
	cin >> m >> n;
	

	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end());

	int left = 0;
	int right = v[v.size() - 1];

	while (left <= right) {
		long long int sum = 0;
		int mid = (left + right) / 2;
		for (int i = 0; i < m; i++) {
			if (mid < v[i]) {
				sum = sum + (v[i] - mid);
			}
		}
		if (sum >= n) {
			ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << ans;
}