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

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

2343번: 기타 레슨

---

문제해석

---

비디오의 개수와 블루레이의 개수를 입력 받은 후 비디오의 길이를 각각 입력받고, 블루레이에 비디오를 분배 하였을 때, 블루레이의 최솟값을 구하는 문제이다.

 

---

코드

---

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
int N, M;
int a[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int max, min = 0;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		max += a[i];	
	}
	min = *max_element(a, a + N);	

	while (min <= max) {	
		int mid = (min + max) / 2;	

		int sum = 0, count = 0;	
		for (int i = 0; i < N; i++) {
			if (sum + a[i] > mid) {
				sum = 0;
				count++;
			}
			sum += a[i];
		}
		if (sum != 0) count++;	
		
        	
		if (count > M) {
			min = mid + 1;
		}
		else {
			max = mid - 1;
		}
	}
    
	cout << min;
	return 0;
}

---

문제풀이

---

먼저 입력 수의 범위를 살펴보았을 때 100000 이하로 나타나져 있기 때문에 이분탐색으로 풀어야 한다는 것을 미리 깨달아야 한다.

그렇게 판단 후 문제를 풀어보면, 비디오 개수 (N) 블루레이 개수 (M) 각각의 비디오 길이 배열a 를 입력 받고 가장 최대크기의 블루레이 크기가 될 수 있는 모든 비디오들의 길이를 합한 값을 max라는 변수에 저장해주고, 가장 작은 블루레이 크기가 될 수 있는 비디오 길이중 가장 긴 값을 min에 넣어준다.

그런 후, max값이 min값보다 같거나 클때 동안 다음 과정을 반복해주면 되는데, 임의로 우리가 지정한 mid라는 블루레이의 크기 값에 비디오들을 하나씩 넣어보며 만약 값이 더 크게 되면 필요한 블루레이 갯수를 한개 증가시켜준다. 그렇게 계속해서 비디오를 넣어보며 합을 구해주고 그 합을 활용해 큰지 적은지 판단하여 둔다. 모든 비디오를 다 넣어준 후에 count 한 블루에이 개수가 M보다 크면 기존 블루레이 개수를 늘려주고 적으면 줄여준다.

그렇게 한 후 최종 답이 들어있는 변수인 min을 출력해주면 해결할 수 있는 문제이다.