[BOJ]백준 2805번: 나무 자르기(C++) / 이진탐색

www.acmicpc.net/problem/2805

2805번: 나무 자르기

내가 기존에 못 하던 유형인 DP, 이진탐색을 연습할 필요성을 느껴서 간간히 풀어보려고 한다

대표적인 문제인 나무자르기

사실 옛날에는 봐도 감이 안 와서 몇번을 풀려고 트라이했지만 실패했었는데

스터디에 이진탐색 빡고수분의 지도를 몇 번 받아 이제 감이 슬슬 오고있따

이진탐색 문제는 left, right 변수를 설정하는 것이 가장 핵심인 것 같다.

처음부터 이진탐색 솔루션이 떠오르는게 어렵다면 완전탐색으로 문제를 설계해놓고 탐색의 범위를 줄일 수 있는 변수를 찾는 것도 좋은 생각이 아닐까?(아직 많이 안 풀어봐서 모름)

그래도 이 문제는 바로 절단기의 높이 변수 H를 binary search key로 둬야겠다는 생각이 들었다

그리고 DP, 이진탐색 특성 상 입출력 값이 엄청나게 커질 수 있기 때문에 자료형을 잘 선택하는게 중요하다 !!

#include <cstdio>
#include <vector>
#define ull unsigned long long
using namespace std;

vector<int> tree;
int n, m, left, right, ans;

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0,th; i < n; i++) {
		scanf("%d", &th);
		tree.push_back(th);
		if (th > right)right = th;
	}

	while (left <= right) {
		int h = (left + right) / 2;

		ull sum = 0;
		for (int i = 0; i < n; i++)
			if (tree[i] > h)sum += (ull)tree[i] - h;

		if (sum >= m) {
			left = h + 1;
			if (h > ans)ans = h;
		}
		else right = h - 1;

	}
	printf("%d", ans);
	return 0;
}