이코테 떡볶이 떡 만들기

코드

: 재귀로

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#include <map>
#include <algorithm>
#include <numeric>


int height = 0;

void func(vector<int>&v, int target, int start , int last)
{
	if (start > last)
		return;

	int mid = (start + last) / 2;
	// mid 을 그대로 빼자.

	int result = 0;
	for (int i = 0; i < v.size(); i++)
	{
		int cut = v[i] - mid;

		if (cut > 0)
			result += cut;
	}

	// 일단 cut이 무조건 target 값보다 동일하거나 같아야 함.
	if (result >= target)
	{
		height = mid;
		func(v, target, mid + 1, last);
	}
	// target에 도달하지 않으면,
	// mid를 낮춰야 함.
	else
	{
		func(v, target, start, mid - 1);
	}

	//값에 미치지 못하면 아예 종료..
	//값에 미치면 h를 최대값으로 구해야 하므로.. 
	//재귀로 진행하자.
	
}


int main()
{
	// 손님이 원하는 m만큼의 떡을 얻어야 하는 절단기 높이의 최대값..
	int n, m;

	cin >> n >> m;

	vector<int>v(n, 0);


	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	sort(begin(v), end(v));

	// 일단 재귀
	// 가운데 값을 기준으로 해서 모든 거를 뺌.
	//[0] 과 [size] - 1 을 먼저 보내면서 시작하자.

	func(v, m, v[0], v[v.size() - 1]);

	cout << height << endl;
}