[백준] 2805번: 나무 자르기 C++로 풀어보기

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

2805번: 나무 자르기

 

2805번 설명

생각

이분탐색을 이용해보자.

1. 나무의 높이들을 입력받아 벡터에 넣고 그 벡터를 오름차순으로 정렬한다.

2. 잘라진 나무의 높이의 합을 입력받는 변수(cnt)를 하나 생성한다.

3. 벡터의 루프를 돌면서 잘라진 나무의 합을 구한다.

4. 처음(st)을 1, 끝(en)을 벡터의 back()으로 놓는다.

5. mid = (st + en + 1) / 2로 놓는다. (1을 더하는 이유는 무한루프를 피하기 위해서다.)

6. 자른 나무의 합이 m보다 같거나 크다면

7. st = mid + 1로 놓는다.(절단기의 높이를 높여준다. 만약에 같다면 루프의 조건으로 인해 루프가 끝날 것이다.)

8. 만약 자른 나무의 합이 m보다 작다면

9. en = mid - 1로 놓는다.(절단기의 높이를 낮춰준다.)

 

코드

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

vector <ll> v;

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

	ll n, m;
	ll ans = 0;
	cin >> n >> m; // n = 나무의 수, m = 가져가려고 하는 나무의 길이

	while (n--) { // 나무의 높이 입력
		ll x;
		cin >> x;
		v.push_back(x);
	}

	sort(v.begin(), v.end()); // 오름차순 정렬

	ll st = 1;
	ll en = v.back();


	while (st <= en) {
		
		ll cnt = 0;
		ll mid = (st + en + 1) / 2;
		for (auto it = v.begin(); it != v.end(); it++) {
			ll isit = *it - mid; // 나무의 높이에서 절단기의 높이를 뺀다.
			if (isit > 0) { // 0보다 크다면
				cnt += isit; // 더해준다
			}
		}
		if (cnt >= m) { // 자른 나무의 합이 m과 같거나 크다면
			ans = mid;
			st = mid + 1; // 절단기의 높이를 높여준다.
		}
		else { // 자른 나무의 합이 m보다 작다면
			en = mid - 1; // 절단기의 높이를 낮춰준다.
		}
	}

	cout << ans;

}

 

결과

2805번 결과