문제

2805번: 나무 자르기

풀이

• 나무 전체 길이 합이 int 범위를 넘어가기 때문에
• long long 으로 해줘야한다.
• left 이상 right 미만으로 풀었다.

구현

#include <iostream>

using namespace std;

int n;
long long m;
int wood[1000001];
int wood_max;

int rec(long long left, long long right) {
	long long sum;
	long long mid;

	mid = (left + right) / 2;
	if (right <= left + 1)
		return (mid);
	sum = 0;
	for (int i = 0; i < n; i++)
		if (wood[i] - mid > 0) sum += wood[i] - mid;
	return (sum < m ? rec(left, mid) : rec(mid, right));
}

int solve() {
	return (rec(0, wood_max + 1));
}

int main() {
    wood_max = -1;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> wood[i];
		if (wood_max < wood[i]) wood_max = wood[i];
	}
	cout << solve() << endl;
	return (0);
}