[백준 16401] 과자 나눠주기

조카에게 줄 수 있는 과자의 최대 길이 이므로 일단 답은 한 개

즉 최대 길이를 쭉 찾다가 딱 최대 길이가 안될때 그 직전의 값이 답이다

그러니까 그 경계를 찾으면 됨.

 

오랜만에 시간복잡도를 계산해보면

특정 값으로 과자 조각내는거 계산하는데 O(N), 이분탐색 O(logN)이므로 총 O(N)*O(logN).

지수시간이므로 1초안에 가뿐히 통과가능하다.

 

---

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

#define SIZE 1000000

using namespace std;

int M, N;
vector<int> arr;

// O(N)
int check(int k) {
	int ret = 0;
	for (int i = 0; i < N; i++) { ret += arr[i] / k; }
	return ret;
}

// O(logN)
int binary_search(int n) {

	int left = 1;
	int right = n;
	int ans = 0;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid) >= M) {
			left = mid + 1;
			ans = mid;
		}else {
			right = mid - 1;
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int x;
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		cin >> x;
		arr.push_back(x);
	}

	sort(arr.begin(), arr.end());
	cout << binary_search(arr[N - 1]);

	return 0;
}