백준 2805_나무 자르기(C++)

 

www.acmicpc.net/problem/2805

2805번: 나무 자르기

[문제 풀이]

이분 탐색을 이용하여 문제를 풀었습니다.

이 문제는 M 미터의 나무를 구하기 위해 절단기가 가질 수 있는 최고 높이 H를 구하는 문제였습니다.

 

알고리즘 문제에서 00 자르기라는 문제는 이분탐색을 이용하는 문제가 많습니다. 이 문제 또한 이분 탐색을 이용하는 문제였습니다. 

 

아이디어

• 최고 높이 H는 0 ~ (나무 최대 높이) 사이에 존재한다.  
• H를 구하기 위해서는 0 ~ (나무 최대 높이)의 값들을 이분 탐색을 통해 구해준다.

이용한 로직

• 이분탐색을 위해 나무 배열을 정렬합니다.  
• left = 0, right = (나무 최대 높이)로 초기화합니다.
• 이분탐색을 하며 자른 나무가 M미터 보다 작을 경우 작은 값을 찾아줍니다.
• 이분탐색을 하며 자른 나무가 M미터 보다 클 경우 값을 비교해줍니다.

[코드]

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

long long N, M, answer = 0;

vector<long long> arr;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (long long i = 0; i < N; i++) {
		long long temp;
		cin >> temp;

		arr.push_back(temp);
	}

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

	long long left = 0;
	long long right = arr[N - 1];

	while (left <= right) {

		long long sum = 0;
		long long mid = (left + right) / 2;
		
		for (int i = 0; i < N; i++) {
			if ((arr[i] - mid) > 0)
				sum += (arr[i] - mid);
		}

		if (sum < M) {
			right = mid - 1;
		}
		else if (sum >= M) {
			if (answer < mid)
				answer = mid;
			left = mid + 1;
		}

	}

	cout << answer << endl;

	return 0;

}