Baekjoon 2805 나무 자르기

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

소스결과 5896 KB / 180 ms

출처 Baekjoon, COCI 2011/2012 Contest #5

언어 C++ 17

분류 이분 탐색

 

설명

환경에 관심 많은 상근이가 목재 절단기를 이용해 나무를 잘라 원하는 길이를 가져가기 위해 설정 하는 높이의 최대 값을 구하자

 

환경에 관심이 많으면 나무를 자르지 말지.. 왜 고통스럽게 ㅠㅠ

이분 탐색 문제라는 느낌이 들지만 기준을 잡기 너무 어렵다. 그리고 범위를 이동 시키는 방법도.. 이해가 잘 안가지만..

처음에는 주어지는 나무 길이를 오름차순으로 정렬해 최소, 최대 값 사이중에 경계선 부분을 찾아내는 방법인줄 알았으나..

그냥 설정 할 수 있는 최대 범위를 설정해 이분 탐색을 진행해 최대, 최소가 역전되는 현상이 나타낼 떄까지 보는 구현이 추가된 이분탐색이었다.

결론은 나무를 자를 때 잘리는 나무와 잘리지 않는 나무를 구분해 총 합을 구하는 부분만 구현하고 그 값을 기준으로 이분 탐색을 진행하면 되는 문제다.

 

나는 아직 멀었나보다..

 

알고리즘

1. 나무 개수와, 목표 값, 각 나무의 길이를 받는다.

2. 0 ~ 10^9+1 의 범위를 최소, 최대로 지정하고 중간값을 구해 절단기 높이로 지정한다.

3. 지정된 절단기 높이를 기준으로 구해지는 나무의 값을 계산하고 결과값과 목표 값을 비교해 범위를 재 지정한다.

4. 최대, 최소가 역전되면 결과값을 출력한다.

 

소스코드

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

using namespace std;

long long remain(vector<int>& vec, int val)
{
	long long sum = 0;

	for (int i = 0; i < vec.size(); i++)
		if (vec[i] > val)
			sum += (vec[i] - val);
	return sum;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	long long n, m;
	cin >> n >> m;

	vector<int> woods(n);

	for (int i = 0; i < n; i++)
		cin >> woods[i];
	
	int left = 0, right = 1000000005;
	int res = 0;
	while (left <= right)
	{
		int middle = (left + right) / 2;

		if (remain(woods, middle) >= m)
		{
			left = middle + 1;
			res = max(res, middle);
		}
		else
		{
			right = middle - 1;
		}
	}
	cout << res;

	return 0;
}