[C] 백준 - 2805번: 나무 자르기

4월 17일(수) - 이분 탐색 (2805번)

2805번: 나무 자르기

---

최초 생각 정리

---

문제점

1. int 범위 -> long long 범위

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

long long N, M;
long long tree[1000001];
long long total, mid, result, max = 0;

void binary_search(long long tree[], long long left, long long right)
{
	if (left > right)
	{
		return;
	}

	total = 0;
	mid = (left + right) / 2;
	for (int i = 0; i < N; i++)
	{
		if (tree[i] > mid)
		{
			total = total + (tree[i] - mid);
		}
	}

	if (total < M)
	{
		binary_search(tree, left, mid - 1);
	}
	else
	{
		result = mid;
		binary_search(tree, mid + 1, right);
	}
}

int main(void)
{
	scanf("%lld %lld", &N, &M);

	for (int i = 0; i < N; i++)
	{
		scanf("%lld", &tree[i]);

		if (max < tree[i])
		{
			max = tree[i];
		}
	}
	
	binary_search(tree, 0, max);
	printf("%lld", result);

	return 0;
}

---