[백준/C++] 2343번: 기타 레슨

https://www.acmicpc.net/problem/2343

2343번: 기타 레슨

• 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdio.h>
#include <queue>
#include <vector>
#include <unordered_map>
#include <set>
#include <map>
#include<cmath>
#define LL long long
using namespace std;
LL arr[100001];

int main() {
	cin.tie(NULL);
	int n = 0;
	int m = 0;
	cin >> n >> m;
	LL l = 0;
	LL r = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		r += arr[i];
		if (l < arr[i]) l = arr[i];
	}
	
	LL mid = (l + r) / 2;

	LL ans = r+1;
	while (l <= r) {
		
		int cnt = 0;
		LL br = 0;
		for (int i = 0; i < n; i++) {

			if (br+arr[i] <= mid) {
				br += arr[i];
			}
			else if (br + arr[i] > mid) {
				br = arr[i];
				cnt++;
			}
		}

		cnt++;
	
		if (cnt > m) {
			l = mid + 1;
		}
		else if (cnt <= m) {
			if (mid < ans) ans = mid;
			r = mid - 1;
		}
		mid = (l + r) / 2;
	}
	cout << ans << endl;
	
		
	return 0;
}

• 알고리즘 분류: 이분 탐색
• 문제 해설

이분 탐색의 mid 조건을 블루레이 크기로 잡아야하는 문제였다. 최소 블루레이 크기와 최대 블루레이 크기는 각각 배열에서 가장 큰 요소(아예 담지 못하는 경우를 배제), 모든 블루레이의 요소 합이 된다.

그 다음 정렬 같은 것을 하지 않고 그냥 처음부터 순서대로 담아보면 된다. 순서대로 담았을 때 블루레이 개수가 원하는 값보다 작으면 블루레이 크기를 줄인다. 이때 블루레이 크기가 최소 일수도 있으니 갱신해준다. 블루레이 개수가 원하는 값보다 크면 블루레이 크기를 키워야한다. 이때는 완전히 정답이 될 수 없다.