[백준 17179] 케이크 자르기 (C++)

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

17179번: 케이크 자르기

문제

---

생일을 맞이한 주성이가 생일 파티를 준비하려고 한다. 주성이는 일반 케이크 대신 평소 좋아하던 롤 케이크를 준비했다. 롤 케이크에는 장식이 존재해서 특정 위치에서만 자를 수 있다. 주성이는 롤 케이크 조각을 파티에 올 친구의 수 만큼 준비하고 싶어서, 가장 작은 조각의 크기를 미리 알아보기로 했다. 하지만 짓궂은 주성이의 친구들은 생일파티에 몇 명이 참석하는지 직접적으로 알려주지를 않는다. 그래서 몇 개의 수를 목록에 적어, 각 수만큼 조각을 만들었을 때 가장 작은 조각의 길이의 최댓값을 구하려고 한다.

예를 들어 70cm의 롤 케이크에 자를 수 있는 지점이 5군데(10cm, 20cm, 35cm, 55cm, 60cm)가 있다고 하자. 만약 목록에 적힌 수 중 하나가 3이라면 이때 가장 작은 조각의 길이는 최대 15cm이다. 예를 들어 20cm, 35cm, 55cm 지점을 자를 때 최대가 된다.

 

입력

---

첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000)

다음 M줄에 걸쳐 자를 수 있는 지점을 나타내는 정수 S_i가 주어진다. (1 ≤ S_i < L)

다음 N줄에 걸쳐 자르는 횟수를 나타내는 정수 Q_i가 주어진다. (1 ≤ Qi ≤ M)

S_i는 오름차순으로 주어지고 중복되는 수는 없으며, Q_i도 마찬가지이다.

 

출력

---

N개 줄에 걸쳐 각 목록에 있는 횟수대로 롤 케이크를 잘랐을 때 가장 작은 조각의 길이의 최댓값을 출력한다.

 

문제 풀이

---

이분 탐색 문제.

가장 작은 조각의 길이를 탐색 대상 mid로 잡고, 해당 길이 이상으로 롤케이크를 잘랐을 때 커팅 횟수가 몇 번인지 확인한다.

이전에 자른 지점부터 현재 자를 수 있는 지점까지의 길이가 mid 이상이면 롤케이크를 자를 수 있고 커팅 횟수를 +1한다. 끝 부분 ~ 그 이전 부분도 카운팅되므로 계산되는 커팅 횟수는 실제 커팅 횟수보다 1 더 많다.

해당 길이로 롤케이크를 잘랐을 때 원하는 것보다 커팅 횟수가 많다면 길이를 너무 짧게 잡았다는 뜻이므로 left를 mid+1로 바꾼다. 아니라면 길이를 너무 길게 잡았다는 뜻이므로 right를 mid-1로 바꾼다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, L;
int* arr;
int targetCuttingCount;
int answer;

void binarySearch(int left, int right)
{
	while (left <= right)
	{
		int mid = (left + right) / 2;
		int cuttingCount = 0;
		int cuttingPos = 0;
		for (int i = 1; i < M+2; i++)
		{
			if (arr[i] - cuttingPos >= mid)
			{
				cuttingCount++;
				cuttingPos = arr[i];
			}
		}
		if (cuttingCount > targetCuttingCount)
		{
			left = mid + 1;
			answer = max(answer, mid);
		}
		else
		{
			right = mid - 1;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> L;
	arr = new int[M+2];
	arr[0] = 0;
	for (int i = 1; i < M+1; i++)
	{
		cin >> arr[i];
	}
	arr[M + 1] = L;
	for (int i = 0; i < N; i++)
	{
		cin >> targetCuttingCount;
		binarySearch(1, L);
		cout << answer << "\n";
		answer = 0;
	}
	return 0;
}