BOJ 2343 기타 레슨

www.acmicpc.net/problem/2343

2343번: 기타 레슨

이번에도 파라메트릭 서치 문제다. 이번엔 반복문의 시작을 음반에서 가장 큰 값으로 해줘야 하는데, 우리가 찾으려는 값이 무엇인지 알아야 한다.

문제를 잘 읽어보면 우리는 결국 블루레이의 크기를 찾아야 되는데 여기에 이분 탐색이 사용된다.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

int ar[100001], n, m, sum;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
		sum += ar[i];
	}
	ll L = *max_element(ar, ar + n), R = sum;
	ll ans = 1e9 + 1;
	while (L <= R) {
		ll mid = (L + R) / 2, sum = 0, cnt = 0;
		for (int i = 0; i < n;) {
			sum += ar[i];
			if (sum > mid) {
				sum = 0; cnt++;
			}
			else i++;
		}
		//printf("L= %lld mid= %lld R= %lld sum=%lld cnt=%lld\n", L, mid, R, sum, cnt);
		if (cnt < m) {
			ans = min(ans, mid);
			R = mid - 1;
		}
		else L = mid + 1;
	}
	cout << ans << endl;

	return 0;
}

이분 탐색을 가장 큰 값에서부터 총 합까지 돌려가면서 

		for (int i = 0; i < n;) {
			sum += ar[i];
			if (sum > mid) {
				sum = 0; cnt++;
			}
			else i++;
		}

이것처럼 넣어보고 sum값이 현재 블루레이 값보다 크다면 카운트를 하나 올려준다.

		for (int i = 0; i < n; i++) {
			sum += ar[i];
			if (sum > mid) {
				cnt++; sum = ar[i];
			}
		}
		if (sum <= mid) cnt++;

이런 식으로 구성해줘도 된다.