[C++] 백준 2805번: 나무 자르기

2805번: 나무 자르기

문제 바로가기

이 문제는 1654번: 랜선 자르기와 비슷하다.

그 때에도 탈출조건 때문에 애를 먹었다.

하지만 그 때 되짚어 봤던 것처럼, 

HIGH(또는 RIGHT)에는 MID - 1을,

LOW(또는 LEFT)에는 MID + 1을 대입하고

while문의 조건을 HIGH ≥ LOW로 하면

무한루프에 빠지지 않는다.

또는 

HIGH, LOW = MID로 하되, HIGH > LOW + 1을 while문 조건으로 해도 상관없다.

둘은 사실상 같은거다.

이 문제를 풀면서 이를 잊고 있다가 무한루프로 인한 시간초과가 두 번이나 발생했다.

공식처럼 익혀 놓아야겠다.

#include <cstdio>

int main()
{
	int N, M, MID;
	scanf( "%d %d", &N, &M);

	int LOW = 0;
	int HIGH = 0;
	int* trees = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", trees + i);
		if (trees[i] > HIGH)
			HIGH = trees[i];
	}
	
	while (HIGH >= LOW) {
		MID = (LOW + HIGH) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++)
			if (trees[i] > MID)
				sum += ((long long)trees[i] - MID);
		if (sum < M)
			HIGH = MID - 1;
		else if (sum > M)
			LOW = MID + 1;
		else
			break;
	}
	MID = (LOW + HIGH) / 2;

	printf("%d\n", MID);
	delete[] trees;
	return 0;
}