[C++] 백준 1654번: 탈출 조건에 대하여

1654번: 랜선 자르기

#include <iostream>

using namespace std;

int main()
{
	int K, N;
	scanf("%d %d", &K, &N);
	int* LANs = new int[K];
	long long MAX = 1;
	for (int i = 0; i < K; i++)
	{
		scanf("%d", LANs + i);
		if (LANs[i] > MAX)
			MAX = LANs[i];
	}

	long long MIN = 1;
	long long MID;
	while (MAX >= MIN) {
		MID = (MIN + MAX) / 2;
		long long P = 0;
		for (int i = 0; i < K; i++)
		{
			P += LANs[i] / MID;
		}
		if (P < N) {
			MAX = MID - 1;
		}
		else
		{
			MIN = MID + 1;
		}
	}
	MID = (MIN + MAX) / 2;

	printf("%lld\n", MID);

	return 0;
}

while문에서 조건식이 MAX > MIN 일 때, 답안을 제출하면 오답처리가 된다.

MAX == MIN을 만족할 때까지 반복을 해야한다는 뜻이다.

이를 위해, MAX와 MIN에 MID ± 1의 값을 대입한다.

그렇지 않으면 MIN과 MAX가 1의 차이일 때, 그 간격이 결코 줄어들지 않아 무한루프에 빠진다.

참고