[2805] 나무 자르기 C++

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

-> sum이나 tmp는 int범위를 초과할 수 있어 long long으로 변환 후 통과

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, M;
	int arr[1000001];
	cin >> N >> M;

	long long sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	sort(arr, arr + N);

	if (sum == M) {
		cout << "0";
		return 0;
	}

		int left = 0;
		int right = arr[N - 1];

		int answer;
		while (left <= right) {
			long long tmp = 0;
			int middle = (left + right) / 2;

			for (int i = 0; i < N; i++) {
				tmp += min(arr[i], middle);
			}

			if (sum - tmp >= M) {
				answer = middle;
				left = middle + 1;
			}

			else {
				right = middle - 1;
			}

	}

		cout << answer;
	
	return 0;
}