백준 2805번 나무 자르기(C++)

#include<iostream>
#include<vector>
using namespace std;

vector<int> tree;

int N, M;

bool checkTree(int ch) {
	long long sum = 0;
	for (auto i : tree) {
		if (i - ch > 0)
			sum += i - ch;
	}
	if (sum >= M)
		return true;
	else
		return false;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	cin >> N >> M;
	int max = 0;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		tree.push_back(tmp);
		if (max < tmp) max = tmp;
	}

	int low = 0;
	int high = max;

	while (low <= high) {
		int mid = (low + high) / 2;
		if (checkTree(mid)) low = mid + 1;
		else high = mid - 1;
	}

	cout << high;
}

 

 이분 탐색의 예제로 나오는 기본적인 문제.

받은 나무 중 가장 긴 나무를 high로 두고 low를 0으로 설정한 다음 이분탐색의 방법대로 점점 좁혀나가는 것이 핵심. 이분탐색의 가장 중요한 점은 mid 후  low와 high 를 어떻게 재설정 해가며 확인하느냐가 중요하다. 

 

1. 가장 긴 나무를 high로 두고 이분탐색 시작

2. 지금의 mid = 도끼 라고 생각하고 checkTree에서 지금 도끼로 나무를 잘랐을 때 가능한가? 를 생각해본다.

3. 지금 얻을 수 있는 나무가 원하는 나무보다 적다면? 도끼를 더 밑으로 내려야한다.  high => mid

4. 지금 얻을 수 있는 나무가 원하는 나무와 같거나 많다면? 도끼를 더 위로 올려본다. 어라? 원하는 나무를 얻었는데요? 라고 생각하지말자! 우리는 원하는 것은 나무를 그냥 얻는 것이 아니라 최적! 을 찾아야한다. 올릴 수 있을 때 까지 올려야한다. 

 

그리고 중요한 건 long long 을 사용한다는 건데, int 형은 2^32 -1 까지 표현이 가능하다. 이는 약 20억이다. 20억을 넘어가는 경우가 생길 수 있기 때문에 long long 을 사용해주어야한다.