[Baekjoon] 2805번: 나무 자르기

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

2805번: 나무 자르기

 

---

 

문제 해결 과정

착안

이전 포스트에서의 방법과 동일하게, 이진 탐색(binary search, 이분 탐색) 알고리즘을 응용하여 해결하고자 했다.

 

구현

직전의 포스트에서와 거의 유사한 문제이므로 구체적인 구현 내용은 생략하였다.

 

문제에서 주의할 점은 역시 정수 오버플로(integer overflow)를 염두에 두어 변수의 자료형을 사용해야 한다는 점과, 이진 탐색을 처음 시작할 때의 탐색 구간 설정이다.

* 이번 문제에서는 입력의 수가 많기 때문에 입출력 최적화 코드를 추가하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int N;
unsigned long long M;
unsigned Woods[1000000];

unsigned long long ObtainWoods(unsigned len)
{
	unsigned long long meters = 0;
	for (int i = 0; i < N; i++)
		if (Woods[i] > len)
			meters += Woods[i] - len;

	return meters;
}

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

	cin >> N >> M;

	unsigned minLen = 1;
	unsigned maxLen = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> Woods[i];
		if (maxLen < Woods[i])
			maxLen = Woods[i];
	}

	maxLen++;
	while (minLen < maxLen)
	{
		unsigned middle = (minLen + maxLen) / 2;

		if (ObtainWoods(middle) < M)
			maxLen = middle;
		else
			minLen = middle + 1;
	}

	cout << maxLen - 1 << "\n";
	return 0;
}

 

실행 결과