[백준] 2805번 나무자르기 (이분탐색)

-문제

"틀렸습니다" 나온 이유! 자료형의 중요성!

int 범위 : -2,147,483,648~ 2,147,483,647

높이의 최대 범위가 1,000,000,000 이므로 sum은 int 범위를 넘어서는 경우가 있을 수 있음

int sum  -> long long int sum으로 변경해서 해결함

 

자료형 관련 참고https://melonicedlatte.com/algorithm/2018/03/04/022437.html

 

-코드

#include<stdio.h>
#include<vector>
using namespace std;

int m;
bool cal(int h, vector<int> a)
{
	long long int sum = 0;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] > h) sum += a[i] - h;
	}
	if (sum >= m) return true;
	else return false;
}

int main()
{
	int n, max = 0;
	scanf("%d %d", &n, &m);
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] > max) max = a[i];
	}

	int lt = 0, rt = max, H, res =0;
	while (lt<=rt)
	{
		H = (lt + rt) / 2;
		if (cal(H, a))
		{
			res = H;
			lt = H + 1;
		}
		else
		{
			rt = H - 1;
		}
	}
	printf("%d", res);
	return 0;
}