백준 2805번 - 나무 자르기 (python)

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

2805번: 나무 자르기

 

해당 문제를 작년에 풀려고 했을 때 해당 코드를 작성했었다. (C++로 했으니 양해..)

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

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

	long long n, m; // n = 나무 수, m = 목표 나무 길이
	vector<long long> v;
	long long temp;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}

	long long h = *max_element(v.begin(), v.end());
	
	while (true)
	{
		long long sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (v[i] >= h)
				sum += (v[i] - h);
		}
		if (sum >= m)
		{
			cout << h;
			break;
		}
		h--;
	}
	return 0;
}

 

가장 높은 나무의 길이를 구해서 차례로 하나씩 아래로 내려가게 하는 알고리즘인데..
이렇게 할 경우 시간 복잡도는 O(N)이 된다. 말 그대로 선형 탐색이기 때문이다.

문제에서 높이의 범위가 10억인데, 너무 크다.

이렇게 할 경우 시간 초과가 발생했고, 그렇기에 시간 복잡도를 줄여야한다.

 

이를 위해서는 이분 탐색을 활용하기로 결정했다.

N, M = map(int, input().split())
trees = list(map(int, input().split()))
start = 0
end = max(trees)
h = 0
while start <= end:
    mid = (start + end) // 2
    result = 0
    for tree in trees:
        if tree > mid:
            result += (tree - mid)
    if result < M:
        end = mid - 1
    else:
        h = mid
        start = mid + 1
print(h)

 

사실 이 문제는 전형적인 이분 탐색 문제이다.

높이를 반절씩 줄여나가며, 해당하는 조건에 만족하는지 체크한다.