[백준] 나무 자르기 (2805/C++)

문제

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

2805번: 나무 자르기

풀이

문제를 보면 나무의 높이, 절단기 높이 등 int의 숫자 범위를 넘는다.  또한 적어도+최댓값 등을 찾을 때는 이분 탐색을 의심해보자

 

두 가지 실수하지 않도록 조심하자

1. long long 변수형이 어디 어디에 필요한지

2. 나무절단시 if문을 통해 음수 걸러주기 

 

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int H;
int N;
long long M; //숫자가 너무 큰 탐색 -> 이분탐색 의심
vector<long long> arr;
long long answer;
int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		long long abc;
		cin >> abc;
		arr.push_back(abc);
	}

	sort(arr.begin(), arr.end(),greater<>());

	//이분탐색
	long long low = 0;
	long long high = arr[0];
	while (low <= high) {
		long long middle = (low + high) / 2;
		
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			if(arr[i]-middle>0) sum += arr[i] - middle;

		}
		if (sum >=M) {
			low = middle + 1;
			answer = middle;
		}
		else { // 나무 부족, 절단기 높이 줄임
			high = middle - 1;

		}



	}
	cout << answer;





	return 0;
}