[C/C++] BOJ 2805 :: 나무 자르기

BOJ 2805 :: 나무 자르기

문제 링크 : https://www.acmicpc.net/problem/2805

쉽게 풀릴 것 같이 보이는데 정답 비율이 매우 낮은 문제가 있다.

그거슨.. long long으로 출력하지 않았기 때문일 확률이 매우 높다.. 내가 맨날 실수하는 것을 사람들도 많이 실수하는 듯...

나는 이번 문제에서 두 가지 실수를 하였는데!

첫 번째, 구한 H로 잘랐을 때의 합계가 가져갈 수 있는 합과 같을 때에만 return 하였다 ==> 당연히 fail..

두 번째, int형 변수로 출력하였다 ==> fail.....

두 가지 실수를 만회하였을 때 비로소 성공할 수 있었다 ㅠㅠ 틀렸습니다 몇 번이나 뜬건지 너무 슬프닷..

!!!!! 교훈 !!!!!

예외 조건을 많이 생각해보고 잘 처리하자!!!

주어진 문제의 데이터 범위를 참고하고 자료형을 고려하여 출력하자!!!!

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_2805/BOJ_2805.cpp

// 백준알고리즘 2805번 :: 나무 자르기
#include<iostream>
using namespace std;
int N, M;
int tree[1000001];
// standard로 잘랐을 때의 가져갈 수 있는 나무길이의 합 구하는 함수
long long calc(int standard)
{
	long long sum = 0;
	for (int i = 0; i < N; i++)
	{
		long long available = tree[i] - standard;
		if (available > 0) sum += available;
	}
	return sum;
}
// 절단기에 설정할 수 있는 높이의 최댓값 구하는 함수(이분 탐색)
long long find(int start, int end)
{
	while (1)
	{
		long long middle = (start + end) / 2;
		long long ret = calc(middle);
		if (ret == M) return middle;
		if (start > end) return end;
		// ret가 M보다 작으면 더 밑을 잘라야 한다.
		if (ret < M)
		{
			end = middle - 1;
		}
		// ret가 M보다 크거나 같으면 위를 잘라야 한다.
		else
		{
			start = middle + 1;
		}
	}
}
int main()
{
	long long max_value = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> tree[i];
		if (max_value < tree[i]) max_value = tree[i];
	}
	// 0 부터 나무 최대높이 사이에서 답 구하기
	long long ans = find(0, max_value);
	cout << ans;
	return 0;
}