2805번 나무자르기

문제링크 : www.acmicpc.net/problem/2805

2805번: 나무 자르기

---

---

<알고리즘>

1) H의 범위 지정(최소 : 0, 최대 : 입력값 중 가장 큰 값)

2) 해당 높이일때 가져갈 수 있는 나무의 길이를 계산하는 함수 생성

3) H의 범위를 돌면서 2번 함수를 적용하여 M이상나무를 가져갈 수 있는 가장 큰 H값 찾기

  (정수를 하나씩 늘려가면서 찾으면 너무 오래걸리므로 (O(N) 시간 소요) 이분탐색 알고리즘 이용)

  3-1) (최소+최대)/2 를 중간값으로 보고 중간값의 2번함수 결과가 M보다 크거나 같으면 최솟값 = 중간값+1로

  3-2)  (최소+최대)/2 를 중간값으로 보고 중간값의 2번함수 결과가 M보다 작으면 최댓값 = 중간값-1로

  3-3) 최소>최대가 되면 3번 roop 중지

4) 3-1 과정에서 중간값을 따로 저장해놨다가 그 값을 출력(그냥 중간값 출력시 마지막 범위변화로 인해 달라질 수 있음)

 

 

 

 

 

메모리 : 17648KB      시간 : 692ms

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

long long cutTree(vector<long long > t, int N, int h) {
	long long  total = 0;
	for (int i = 0; i < N; i++) {
		if (t[i] - h >= 0) total += (t[i] - h);
	}
	return total;
}
int main() {
	int N = 0;
	int M = 0;
	cin >> N >> M;

	vector<long long >tree(N);
	int maximum = 0;
	for (int i = 0; i < N; i++) {
		cin >> tree[i];
		if (maximum < tree[i]) { maximum = tree[i]; }
	}

	int left = 0;
	int right = maximum;
	long long  middle = 0;
	long long  length = 0;
	long long  result = 0;
	while (left <= right) {
		middle = ceil((left + right) / 2);
		length = cutTree(tree, N, middle);
		if (length >= M) { 
			result = middle;
			left = middle+1; 
		}
		else { right = middle-1; }
	}

	cout << result;

	return 0;
}