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

Seungbo Shim·2023년 7월 22일

C boj cpp 백준 실버1 알고리즘 이분탐색

Algorithm

목록 보기

2/10

문제 해석

N개의 강의를 M개의 블루레이로 압축하려할 때, 이 때 블루레이의 크기 중 최소를 구한다.
블루레이의 크기는 모두 동일해야 하고, 한 블루레이 안에는 연속된 강의가 들어가야 한다.

9 3
1 2 3 4 5 6 7 8 9

예제를 보았을 때, 용량이 1, 2, 3, 4, 5, 6, 7, 8, 9인 9개의 강의가 있고, 이 강의를 3개의 블루레이로 만드려 한다.
이 때, 블루레이의 크기가 10이라고 치자.
{1, 2, 3, 4}까지는 하나에 담을 수 있겠지만 {5}부터는 하나에 한 강의만 담을 수 있으니 블루레이가 6개나 필요하다.

그렇다면 블루레이의 크기가 20이라면?
{1, 2, 3, 4, 5}, {6, 7}, {8, 9}로 세 개의 블루레이로 압축할 수 있다 😯
그러나 우리가 구해야 할 것은 3개의 블루레이로 압축할 수 있을 때 블루레이의 크기 중 최소값이다.

17

예제의 출력값은 17로, 3개의 블루레이로 압축할 때 블루레이 하나가 가질 수 있는 최소 용량은 17이다.

그래서 어떻게 했는데

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

int N, M;
vector<int> v;
int low, high;

int blueray();

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

	cin >> N >> M;
	high = 0;

	v.resize(N);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
		high += v[i]; // 최대 블루레이 용량: 전체 동영상 용량 합
	}
	low = *max_element(v.begin(), v.end()); // 최소 블루레이 용량: 제일 큰 동영상 용량
	
	cout << blueray();
	return 0;
}

전역변수로 N, M, 동영상의 용량을 저장하는 벡터 v, 블루레이의 최소/최대 용량은 low, high를 선언했다.
main 함수를 먼저 살펴보면, N과 M을 입력받아 벡터 v의 크기를 N만큼으로 설정하였다.

이제 블루레이의 최소 용량을 생각해보자.
물론 1부터 시작할 수는 있지만, 조금이라도 계산량을 줄이기 위해 최소 용량을 max_element,
즉 가장 큰 동영상 크기로 설정하였다. 위의 예제로 생각하면 low=9 로 설정한 것이다.

또한 블루레이의 최대 용량은 한 블루레이에 모든 강의를 담는 것이므로,
v 벡터의 모든 원소의 합으로 설정하였다.

그래서 블루레이의 최소 용량은 어떻게 구하는데용?

int blueray() {
	while (low <= high) {
		int mid = (low + high) / 2;
		int cnt = 0; // 블루레이 개수
		int sum = 0; // 현재 블루레이 하나에 저장된 용량 합

		for (int i = 0; i < N; i++)
		{
			if (sum + v[i] > mid) { // 블루레이 용량을 넘김
				cnt++; // 블루레이 하나 썼다
				sum = 0; // 새 블루레이니까 용량 초기화
			}
			sum += v[i]; // 현재 블루레이에 영상 저장
		}
		if (sum > 0) cnt++; // 용량이 넘치지 않은 마지막 블루레이

		if (cnt <= M) { // M개 이하면 용량이 더 작아야지
			high = mid - 1; // 작은 부분으로 이분탐색
		}
		else { // M개 이상이면 용량을 늘려야지
			low = mid + 1; // 높은 부분으로 이분탐색
		}
	}

	return low;
}

while 문으로 반복하여 이분탐색을 구성했다.
low와 high의 중간값 mid를 설정하고, 요걸 현재 루프의 블루레이 용량으로 생각해보자.

for 문에서는 영상을 블루레이에 담게 된다.
1번부터 영상을 채우며 sum에 용량을 추가해 주는데, 여기서 sum은 지금 채우고 있는 블루레이의 용량이다.
sum이 블루레이 용량 mid를 넘기게 될 때, 방금 채운 블루레이 갯수 cnt를 하나 추가해주고, 새 블루레이를 가져올 거니까 sum=0 으로 초기화 해 준다.

for 문이 끝나 모든 영상을 넣었을 때, 우리는 블루레이를 다 채웠을 때에만 cnt++ 를 해 준 상태이다.
따라서 마지막에 채우고 있던 블루레이가 있었다면 그 갯수를 추가해 준다.

최종적으로 용량이 mid인 블루레이를 cnt개 쓴 상태가 되고,
cnt가 이전에 설정한 M보다 작다면 블루레이 하나의 용량을 작게 하여 더 많은 블루레이를 쓰고,
M보다 크다면 블루레이 하나의 용량을 늘려 더 적은 블루레이를 써야 한다.

마지막 답은 low에 저장되어, low를 반환해준다.

시행착오

오답을 불러온 main 함수는 다음과 같다.

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	cin >> N >> M;
	high = 0;

	v.resize(N);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
		high += v[i];
	}
	sort(v.begin(), v.end());
	low = v[N - 1]; 
	
	cout << blueray();
	return 0;
}