백준 2805번 : 나무 자르기

문제 링크 : www.acmicpc.net/problem/2805

내 풀이(2021.1.17) : 

#include <iostream>
#include <algorithm>

using namespace std;

long long tree[1000000];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	long long M;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> tree[i];
	}

	int start = 0, mid, end = 1000000000;
	long long total_cnt = 0;
	while (start <= end) {
		total_cnt = 0;
		mid = (start + end) / 2;
		for (int i = 0; i < N; i++) {
			long long cut = tree[i] - mid;
			if (cut > 0) total_cnt += cut;
		}
		if (total_cnt == M) break;
		else if (total_cnt > M) {
			start = mid + 1;
		}
		else { // total_cnt < M
			end = mid - 1;
		}
	}

	if (total_cnt < M) cout << mid - 1;
	else cout << mid;

	return 0;
}

STL의 binary_search()로 풀 수 없기 때문에

직접 이분 탐색 알고리즘을 만들어야 하는 문제였다.

 

- 탐색 대상 : total_cnt = 잘린 나무들의 높이의 총합

- 기본 : total_cnt와 M이 같으면 정답

- 주의 : 맨 마지막 탐색 때 total_cnt < M면, mid가 정답보다 한 칸 밀린 위치를 가리키게 됨 (mid - 1을 출력하여 해결)

 

* 이분 탐색 알고리즘은 아예 통째로 외워놓아야 좋다고 한다.