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

 

제출현황

 

문제를 읽고 각각의 나무를 자를 평균값을 초기값 선정을 생각하여

이분탐색을 생각하였고

삽입은 맨 끝으로만 진행하고 삭제는 없기 때문에

STL은 Vector를 선정하였다.

또한 max_element로 최대값을 구할 수 있지만

백트레킹?으로 중간에 목표하는 나무값보다 크다면 종료하여 기준값 변경을 위해

내림차순으로 정렬한 후에 더한 값이 더 커지면 다음 기준값으로 변경하여

시간을 줄여보았다. 

 

sort로 하지않고 이분탐색만 사용을 하였을 때는 164ms가 걸렸지만

 

sort하여 내림차순으로 중간을 넘어갔을때에는

 

156ms로 12ms를 줄여보았다.

아래는 작성한 코드이다.

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

int iNum = 0, iMid = 0, iResult = 0;
long long int iMaxSum = 0;
vector<int> vTree;

void SearchTree()
{
	int iStart = 0, iEnd = vTree[0];
	while (iStart <= iEnd)
	{
		long long int iSum = 0;
		iMid = (iStart + iEnd) / 2;
		for (int i = 0; i < iNum; i++)
		{
			if (vTree[i] > iMid)
			{
				iSum += vTree[i] - iMid;
				if (iSum > iMaxSum)
					break;
			}
		}
		if (iSum < iMaxSum)
			iEnd = iMid - 1;
		else
		{
			iStart = iMid + 1;
			iResult = iMid;
		}
	}
}

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

	cin >> iNum >> iMaxSum;
	vTree.resize(iNum);
	for (int i = 0; i < iNum; i++)
		cin >> vTree[i];
	sort(vTree.begin(), vTree.end(), greater<int>());
	SearchTree();
	cout << iResult << "\n";
}