[BAEKJOON] 2805번 : 나무 자르기

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

typedef long long int INT;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	
	int N, M;

	std::cin >> N >> M;
	INT *trees{ new INT[N] };

	INT Max{ 0 };
	for (int i = 0; i < N; ++i) {
		std::cin >> trees[i];
		Max = std::max(Max, trees[i]);
	}

	INT left{ 0 }, right{ Max };
	INT mid, ans{ 0 }, remain;
	
	while (left <= right) {
		mid = (left + right) / 2;
		remain = 0;

		for (int i = 0; i < N; ++i) 
			if(mid < trees[i]) remain += trees[i] - mid;

		if (remain >= M) {
			ans = std::max(ans, mid);
			left = mid + 1;
		} else {
			right = mid - 1;
		}

	}

	std::cout << ans << '\n';

	delete[] trees;
}

 

풀 이

 

• 목재절단기를 통하여 가장 긴 나무를 얻는 방법은 목재를 자르고 남은 나무를 가지고 필요한 나무를 구하는 방법이다.

• 적어도 M미터의 나무를 집에 가져가는 방법이기 때문에 M미터 이상의 목재가 나와도 된다.

• 위와 같은 조건을 통하여 0부터 가장 큰 나무의 길이의 범위를 이분탐색을 통하여 결과를 찾아내면 된다.

 

출 력 값

 

 

문 제  출 처

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

2805번: 나무 자르기