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

문제

[C++] 백준 2343: 기타 레슨 GOLD 5
https://www.acmicpc.net/problem/2343

 

---

 

접근 방법

이 문제는 N개의 강의를 순서를 유지한 채로 M개의 블루레이에 녹화할 때,

각 블루레이의 최소 용량(길이) 를 구하는 문제다.

 

중요한 점:

• 강의는 나누어 담을 수 없다.
• 순서를 바꿀 수도 없다.
• 블루레이 용량은 모두 동일해야 한다.

그래서 “블루레이 용량이 X일 때, M개 이내로 모든 강의를 담을 수 있는가?”에서
이 값 X를 이분 탐색(Parametric Search) 으로 찾는 식으로 접근했다.

1. 한 블루레이의 최소 용량은 가장 긴 강의 길이보다 작을 수 없다.
   → start = max(vect[i])
2. 한 블루레이의 최대 용량은 모든 강의를 한 장에 몰아 넣는 경우
   → end = 모든 강의 길이의 합

이 구간 [start, end]를 탐색 범위로 두고,
중간 값 mid를 “블루레이 용량”이라고 가정했을 때

• 이 용량으로 강의를 차례대로 채워 넣으면서
• 블루레이가 몇 개 필요한지(cnt)를 계산한다.

cnt가 M보다 크면 → 용량이 너무 작은 것 → start = mid + 1
cnt가 M 이내면 → 용량을 더 줄일 수도 있음 → end = mid - 1

if (cnt > m)
	start = mid + 1;
else
	end = mid - 1;

이 과정을 반복하면 최종적으로 start가 조건을 만족하는 최소 블루레이 용량이 된다.

 

구현 시 주의할 점

• 마지막에 sum이 0이 아니라면,
  아직 사용 중인 블루레이가 하나 더 있는 것이므로 cnt++를 해줘야 한다.

 

---

 

코드

#include <iostream>
#include <vector>
using namespace std;

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

	int n = 0, m = 0;
	cin >> n >> m;

	vector<int> vect(n, 0);
	int start = 0, end = 0;  // 강의 시간 최댓값, 강의 시간 총합
	for (int i = 0; i < n; i++)
	{
		cin >> vect[i];

		if (start < vect[i])
			start = vect[i];
		end += vect[i];
	}
	while (start <= end)
	{
		int mid = (start + end) / 2;
		int sum = 0, cnt = 0;  // 레슨 시간 합, 사용한 블루레이 개수

		for (int i = 0; i < n; i++)
		{
			if (sum + vect[i] > mid)
			{
				cnt++;
				sum = 0;
			}
			sum += vect[i];
		}
		if (sum != 0)
			cnt++;
		if (cnt > m)
			start = mid + 1;
		else
			end = mid - 1;
	}
	cout << start;

	return 0;
}