2805번: 나무 자르기

메모리

시간

8808 KB

264 ms

Code

#include <cstdio>
using namespace std;
int n, m;
long long total = 0;
void get_total(int mid, long long *tree)
{
	total = 0;
	for (int j = 0; j < n; j++)
	{
		if (tree[j] > mid)
			total += tree[j] - mid; 
	}
}
int main()
{
	int mid, max, min;
	int val = 1;
	scanf("%d%d",&n,&m);
	long long tree[n];
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &tree[i]);
		if (tree[i] > max)
			max = tree[i];
	}
	mid = max/2;
	min = 0;
	while (1)
	{
		get_total(mid, tree);
		if (total == m)
			break ;
		if (total > m)
		{
			get_total(mid + 1, tree);
			if (total < m)
				break ;
			min = mid + 1;
			mid = (min + max)/2;
		}
		else
		{
			max = mid - 1;
			mid = (min + max)/2;
		}
	}
	printf("%d", mid);
	return 0;
}

문제 풀이

이진탐색으로 m과 total이 동일할때 까지 범위를 max ~ min 으로 줄여가며 값을 구하였다.

또한 m과 딱 떨어지는 값이 없을 경우도 예외처리 해주었다.

min 을 찾아서 하는 것보다 0 부터 나눠가는게 더 빠름

따로 result 를 저장할 필요없이 left - right 값 중 최소 값을 출력할 수 있다.