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

문제 (https://www.acmicpc.net/problem/2805)

2805번: 나무 자르기

이분 탐색하는 값 (mid): 절단기의 높이

 

절단기의 높이가 mid일 때, 나무를 자르고 남은 길이들의 총합이 m 이상이면?

- 더 큰 mid 값으로 m 이상을 구할 수도 있으므로 start를 mid + 1로 지정한다.

---

[소스코드]

	/* BOJ 2805번: 나무 자르기
	2021-05-25
	Binary Search */
	#include <iostream>
	#include <algorithm>
	using namespace std;
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long n, m, max = -1;
	long long start, end, mid, sum;
	cin >> n >> m;
	int arr[n];
	for(int i = 0 ; i < n ; i++) cin >> arr[i];
	sort(arr, arr+n);
	start = 0;
	end = arr[n - 1];
	while(start <= end){
	sum = 0;
	mid = (start + end) / 2;
	for(int i = 0 ; i < n ; i++){
	if(arr[i] - mid > 0) sum += arr[i] - mid; //자른 나무 길이
	}
	if(sum >= m){
	start = mid + 1;
	if(mid > max) max = mid;
	}
	else end = mid - 1;
	}
	cout << max;
	return 0;
	}

view raw 2805.cpp hosted with ❤ by GitHub

---

2021-05-25

Silver 3

- 이분 탐색

- 매개 변수 탐색