소스 코드

// 이분탐색
#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

int n; // 레슨 수
int m; // 블루레이 개수
vector<int> len; // 레슨 길이
int l; // 최대 len 길이
int r; // len의 sum

void solve();
void input();
int binarySearch();

int main()
{
	//freopen("boj_2343.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();

	return 0;
}

void solve()
{
	input();

	cout << binarySearch() << endl;
}

void input()
{
	cin >> n >> m;
	len = vector<int>(n);

	l = -1;
	r = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> len[i];

		if (len[i] > l)
		{
			l = len[i];
		}

		r += len[i];
	}
}

int binarySearch()
{
	while (l < r)
	{
		int mid = l + (r - l) / 2;

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

		if (cnt == m)
		{
			r = mid;
		}
		else if (cnt < m)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}

	return l;
}

해설

블루레이 크기의 최소값을 찾는 탐색 문제. 블루레이 크기는 최소 CD 길이의 최대값부터 최대 CD길이의 합이므로 정렬된 배열에서 조건을 만족하는 탐색 문제이다. 따라서 이분탐색 알고리즘을 활용할 수 있다.

투포인터 정의
left = CD길이의 최대값
right = CD길이의 합

투포인터 이동 조건
mid 길이의 블루레이가 CD를 담기 위해선 cnt 만큼이 필요할 때
cnt가 목표한 블루레이 개수와 같으면: right = mid
cnt가 목표한 블루레이 개수보다 작으면: right = mid - 1
cnt가 목표한 블루레이 개수보다 크면: left = mid + 1