[Baekjoon] 17179번: 케이크 자르기

https://www.acmicpc.net/problem/17179

17179번: 케이크 자르기

 

---

 

문제 해결 과정

착안

자르고자 하는 케이크 조각 수를 만족하기 위해 자연수 1부터 $L$까지의 길이 중 가능한 길이의 최댓값을 이진 탐색(binary search, 이분 탐색)을 응용하여 구한다.

 

구현

편의상 시작 탐색 구간의 우측 끝값을 불가능한 길이인 $L+1$로 설정하여 탐색을 시작하고 아래 코드와 같이 탐색 알고리즘을 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Points[1002];
int N, M, L;

bool Cuttable(int len, int count)
{
	int cnt = 0;
	int start = 0;
	for (int i = 0; i <= M + 1; i++)
	{
		if (Points[i] - Points[start] >= len)
		{
			cnt++;
			start = i;
		}
	}

	return cnt >= count;
}

int BinarySearch(int left, int right, int count)
{
	while (left < right)
	{
		int len = (left + right) / 2;
		if (Cuttable(len, count))
			left = len + 1;
		else
			right = len;
	}

	return right - 1;
}

int main()
{
	cin >> N >> M >> L;

	Points[M + 1] = L;
	for (int i = 1; i <= M; i++)
		cin >> Points[i];

	while (N--)
	{
		int CutCount;
		cin >> CutCount;
		cout << BinarySearch(1, L + 1, CutCount + 1) << "\n";
	}
	
	return 0;
}

 

실행 결과