[백준] 17179 케이크 자르기💫

백준 17179 케이크 자르기

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

• 왜... 틀렸을까...

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

//최적화 문제: 롤케이크를 cut번 잘랐을 때, 가장 작은 조각의 길이의 최댓값을 구하라
//결정 문제: 롤케이크 조각의 길이가 x 혹은 x 이상이 되도록 cut번 자르는 방법이 존재하는가?

int n, m, l, cut;
vector<int> pos;

bool decision(double x) {
	int possiblecut = 0;

	int prev = 0;
	for (int i = 0; i < pos.size(); ++i) {
		int cur = pos[i];

		//cur 위치에서 자른다면 만들어질 케이크 조각의 길이 >= x
		//cur 위치에서 자른다면 남은 롤케이크의 길이 >= x 
		if ((cur - prev >= x) && (l - prev >= x)) {
			prev = cur;
			possiblecut++;
		}
	}

	return possiblecut >= cut;
}


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

	cin >> n >> m >> l;

	for (int i = 0; i < m; ++i) {
		int input;
		cin >> input;
		pos.push_back(input);
	}

	for (int i = 0; i < n; ++i) {

		cin >> cut;

		double hi = l;
		double lo = 0;
		for (int it = 0; it < 100; ++it) {
			double mid = (hi + lo) / 2;

			if (decision(mid)) 
				lo = mid;
			else 
				hi = mid;
		}

		cout << (int)lo << "\n";
	}

	return 0;
}