[백준] 나무 자르기(2805) *

나무를 위에서부터 잘라서 적어도 M미터의 나무를 집으로 가져가야 할 때 높이의 최댓값을 구하는 문제이다.

간단하게 위에서부터 모두 확인하면 문제를 해결할 수 있어 보이지만... 이 문제의 입력값을 잘 보아야 한다.

 

나무의 길이(20억까지)

나무의 수(100만까지)

 

for문으로 일일이 전부 다 확인하면 무조건 시간초과가 발생할 것이다.

그렇다면 이 문제는 어떻게 해결해야 하는가??

이분탐색을 이용해서 해결하면 된다.

이분탐색이란 L와 R 그리고 mid의 값을 가지고 왼쪽으로 갈지 오른쪽으로 갈지 확인하는 것이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

long long arr[1000001];

int main(void)
{
	long long N = 0;
	long long M = 0;
	long long sum = 0;

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	long long start = 0;
	long long end = 1000000000;
	long long mid = 0;

	long long result = 0;

	while (start <= end)
	{
		mid = (start + end) / 2;
		sum = 0;

		for (int i = 0; i < N; i++)
		{
			if (arr[i] > mid)
			{
				sum = sum + arr[i]-mid;
			}
		}

		if (sum == M)
		{
			result = mid;
			break;
		}
		else if (sum > M)//클때만 원하기 때문에 여기서만 result를 갱신
		{
			start = mid + 1;
			if (result < mid)
			{
				result = mid;
			}
			
		}
		else
		{
			end = mid - 1;
		}

	}

	cout << result;

	return 0;
}

 

문제풀이방법

1.Start가 End보다 작거나 같을 때까지 while문을 반복한다.

2.mid의 값을 구하고 이 값을 이용해서 가져갈 수 있는 나무를 저장한다.

3. 만약 가져갈 수 있는 나무와 원하는 값이 딱 맞아떨어지면 바로 break 한다.

4. 딱 맞아떨어지지 않고 가져갈 수 있는 나무의 값이 M보다 더 크면 start의 값을 mid의 한 칸 오른쪽으로 옮긴다.(그래야 다음번에 가져갈 수 있는 나무의 값이 작아지기 때문)

5. 딱 맞아떨어지지 않고 가져갈 수 있는 나무의 값이 M보다 더 작으면 end의 값을 mid의 한 칸 왼쪽으로 옮긴다.(그래야 다음번에 가져갈 수 있는 나무의 값이 커지기 때문.) 결국 높이의 최댓값을 찾는 문제임.

 

기본적으로 이분탐색 문제는 정렬이 필요로 하는데 이 문제의 경우에는 정렬을 하지 않고도 풀 수 있다.