7-2 떡볶이 떡 만들기

이진 탐색 문제) 떡볶이 떡 만들기

1. 문제

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.
절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 이걸 처리 안 해줘서 시간을 허비했다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1<=N<=1,000,000, 1<=M<=2,000,000,000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

3. 출력

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

4. 풀이

• 이진 탐색 대표 문제
• 자를 높이를 이진 탐색으로 조정한다.
• 자르고 남은 떡을 모아서 손님이 원하는 떡의 길이와 비교한다.
• 자르고 남은 떡이 손님이 원하는 길이보다 짧으면 손님은 집에 안 간다. -> end를 변경하여 이진탐색을 새로 해주어야 한다.
• 자르고 남은 떡이 손님이 원하는 길이보다 같거나 길면 손님은 집에 갈 수 있다.
• 하지만, 그거보다 더 적합한 값이 있을 수도 있으니 현재 높이를 최대로 가정하고, start를 변경한 이진탐색을 한다.

5. 처음 코드와 달라진 점

• height보다 짧은 떡을 0으로 처리하도록 변경하였다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int max_height=0;
vector<int> ricecakes;

void  binarySearch(int target, int start, int end) {
	if (start > end) return;
	int height = (start + end) / 2;
	int sum = 0;

	for (int ricecake : ricecakes){
		int rest = ricecake - height < 0 ? 0 : ricecake - height;
		sum += rest;
	}

	if (target > sum) binarySearch(target, start, height - 1);
	else {
		max_height = max(max_height, height);
		binarySearch(target, height + 1, end);
	}
	return;	
}

int main() {
	int answer;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++){
		int tmp;
		cin >> tmp;
		ricecakes.push_back(tmp);
	}
	int max = *max_element(ricecakes.begin(), ricecakes.end());
	binarySearch(m, 0, max);
	cout << max_height<<endl;
}