[백준 2805] 나무 자르기

문제 링크 => 2805번: 나무 자르기 (acmicpc.net)

2805번: 나무 자르기

---

처음으로 접한 이분탐색 문제가 이 문제인거 같다.

 

나무를 자르는 범위를 first ~ end사이에 존재한다고 할 때 다음과 같은 과정을 통해 구해주도록 한다.

(이때 first = 0, end = 나무들 중에 최댓값)

 

(1) 범위의 first 값이 end 값보다 큰 경우가 아닐 경우 계속해서 찾아주도록 한다.

 

(2) first 값과 end 값 사이의 값을 mid 라고 할 때, 나무들과 mid 값을 각각 비교하여 mid 값이 나무보다 작은 경우에 대해서 (나무의 길이 - mid) 값을 total 값에 더해가도록 한다.

 

(3) total 값이 m 보다 작은 경우 total 값을 크게하기 위해서 end = mid - 1 을 해주고

total 값이 m 보다 크거나 같은 경우 total 값을 작거나 유지하도록 하기 위해서 first = mid + 1 을 해준다.

 

위 과정을 반복하여 나온 first, end값에 대하여 설정할 수 있는 최종 높이는 (first+end)/2 값이 된다.

 

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

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

void input() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		long long x;
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());
}

void solve() {
	long long first = 0, end = v[v.size() - 1];
	while (first <= end) {
		long long total = 0;
		long long mid = (first + end) / 2;
		for (int i = 0; i < v.size(); i++) {
			total += (v[i] <= mid ? 0 : v[i] - mid);
		}
		if (total < m) {
			end = mid - 1;
		}
		else {
			first = mid + 1;
		}
	}
	cout << (first + end) / 2;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();
	
	return 0;
}