[백준/C++] 17179번: 케이크 자르기

문제

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

17179번: 케이크 자르기

---

문제 요약

길이가 L인 롤 케이크가 있고, 이 케이크에는 자를 수 있는 지점이 M군데 존재한다.

 

자르는 횟수가 주어졌을 때, 가장 작은 조각의 길이의 최댓값을 출력한다.

---

코드

#include<iostream>

using namespace std;

#define MAX 1000

int n, m, length;

int point[MAX]; // 자를 수 있는 지점 저장
int target[MAX]; // 잘라야 하는 횟수

void binarySearch() {
	for (int j = 0; j < n; j++) {
		int left = 0;
		int right = length;

		while (left <= right) {
			int mid = (left + right) / 2; // 가장 작은 조각의 길이의 최대 값
			int prev = 0; // 마지막으로 자른 위치
			int cut = 0; // 자를 수 있는 횟수

			// mid보다 긴 구간을 자를 수 있는 개수 구하기
			for (int i = 0; i < m; i++) {
				if (point[i] - prev >= mid) { // 자른 길이가 mid 보다 크면
					prev = point[i]; // prev에 자른 위치 저장 (자른 상태)
					cut++; // 자를 수 있는 횟수 증가
				}
			}

			// 잘라야하는 횟수와 자를 수 있는 횟수가 같은데, 마지막 조각의 길이가 mid보다 작거나
			// 자를 수 있는 횟수보다 잘라야하는 횟수가 더 많으면,
			if ((target[j] == cut && length - prev < mid) || cut < target[j]) {
				right = mid - 1; // 가장 작은 조각의 길이를 줄인다. -> 자를 수 있는 횟수 증가
			}
			else {
				left = mid + 1; // 가장 작은 조각의 길이를 늘린다. -> 자를 수 있는 횟수 감소
			}
		}
		cout << right << "\n";
	}
}

int main() {
	//자르는 횟수 목록 길이. 자를수 있을 수 있는 지점 수, 롤 케이크 길이
	cin >> n >> m >> length; 

	for (int i = 0; i < m; i++) {
		cin >> point[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> target[i];
	}
	
	binarySearch();

	return 0;
}

---

코드 설명

1. 정보를 입력 받는다.

 

1 - 1.자르는 횟수가 담긴 목록의 길이 N과, 자를 수 있는 지점의 개수 M, 롤 케이크의 길이 L을 입력 받는다.

 

1 - 2. 자를 수 있는 지점을 나타내는 정수를 입력 받고, 배열 point에 저장한다.

 

1 - 3. 자르는 횟수들을 입력 받고, 배열 target에 저장한다.

 

2. 이진 탐색을 진행한다.

 

2 - 1. 가장 작은 조각의 최대 길이를 mid로 설정하고, left는 0, right는 L, 즉 L의 절반부터 탐색한다.

+ left 포인터가 right 포인터의 왼쪽에 있을 동안만 탐색한다.

 

2 - 2. 자를 수 있는 지점을 하나씩 체크하여 mid보다 긴 구간이 발생하면 (자를 수 있으면) prev변수에 위치를 저장하여 자른다. (자를 때마다 cut을 1씩 증가시키며 자른 횟수 체크)

+ point[i] - prev는 현재 체크하는 자를 수 있는 지점에서 가장 최근에 잘랐던 지점을 뺀 값. 즉 point[i] 구간을 잘랐을 경우 구간 길이

 

2 - 3. 자를 수 있는 횟수(cut)보다 잘라야 하는 횟수(target[j])가 더 많으면 가장 작은 조각의 최대 길이를 줄여 자를 수 있는 횟수를 증가시키고, 더 적으면 가장 작은 조각의 최대 길이를 늘려 자를 수 있는 횟수를  감소시킨다.

 

+ 2 - 2에서 마지막 조각의 길이는 고려하지 못하므로, 잘라야하는 횟수와 자를 수 있는 횟수가 같으나, 마지막 조각의 길이가 mid보다 작다면 (가장 작은 조각의 길이가 mid가 아니므로)  가장 작은 조각의 최대 길이를 줄인다.

 

+ 조건에서 cut  <= target[j]이 아닌 이유는 최대 길이을 구하는 문제이기 때문이다.

target[j]에 해당하는 길이를 찾았을 때, 더 긴 길이도 가능한지 탐색을 해야한다.

 

+  right를 출력하는 이유는 target[j]에 해당하는 길이를 찾았을 때, (cut == target[j]일 경우) left가 갱신, right는 고정이다, left가 right보다 클 때, 반복이 종료되므로 최종 길이는 right에 존재한다.

 

참조: https://kau-algorithm.tistory.com/344