BOJ 2343 | 기타 레슨

Parametric Search를 사용하여 푸는 문제이다.

처음에는 녹화되는 강의는 연속적이어야 한다는 조건을 못 보고 그리디하게 풀면 안 되는 문제인 줄 알았는데 사실 쉬운 문제였다.

가능한 블루레이 크기 중 최소이고, F~T 분포인 결정 문제이다.

lower_bound() 쓰면 간단하지만 그래도 직접 check() 함수를 구현해서 풀어보았다.

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> lecture;

bool check(int len){
	int box = 0;
	int cnt = 1;
	for (auto i : lecture){
		
		if (i > len){ // 현재 box가 감당할 수 없는 element가 있을 때
			return false;
		}
		
		if (box + i <= len){
			box += i;
		} else{ // new box
			box = i;
			cnt++;
		}
	}
	
	if (cnt <= M)
		return true;
	else return false;
}

int main(){
	
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		lecture.push_back(t);
	}
	
	int lo = 0;
	int hi = 1e9+1;
	
	while (lo + 1 < hi) {
		int mid = (lo+hi)/2;
		if (check(mid)) hi = mid;
		else lo = mid;
	}
	
	cout << hi;
	
}

lecture의 원소가 mid 값보다 큰 경우를 생각하지 않아 한 번 틀렸다.
실수를 줄이는 것이 항상 어렵다.