백준 - 2343(기타 레슨) - C++

hansol_Shin·2021년 7월 7일

백준 알고리즘

Algorithm

목록 보기

11/12

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

문제 설명

레슨 비디오의 개수와 이를 나눠담을 블루레이의 개수가 순서로 들어온다. 이후 각 비디오의 길이가 순차적으로 입력된다.
이때, 레슨 비디오를 블루레이 개수에 알맞게 넣을 때 블루레이의 최소값을 구한다. 단, 모든 블루레이의 길이는 똑같다.

예제 입력
9 3
1 2 3 4 5 6 7 8 9
예제 출력
17

예제 설명
3개의 블루레이에 비디오를 담으면 1,2,3,4,5 -> 15 | 6,7-> 13 | 8,9->17 로 담을 수 있다. 그리고 이때, 3개의 비디오 길이 중 최대인 17이 블루레이의 길이가 되고, 이때 가장 최소의 길이가 된다.

접근 방법

N과 M이 100000이하의 자연수이기 때문에 효율성을 따져야한다.
따라서 문제는 이분 탐색으로 풀이한다.

이분 탐색의 가장 중요한것은 기준을 무엇으로 잡느냐? 즉, l,r,mid이 무엇을 가르키는지이다.
이 문제에서 기준은 블루레이의 길이로 잡으면 가능하다.
블루레이의 기준을 최소인 l과 최대인 r로 해주면 가능하고, 이때 최소는 입력받은 배열의 최대값이 되어야 모든 비디오를 담을수 있다. 최대는 입력받은 배열의 총 합이 되어야 하나의 블루레이에 담을 수 있다.
while문 안에서 mid의 길이로 배열을 담을 때 필요한 블루레이수 cnt를 센 후, M과 비교하여 cnt가 크면 블루레이 길이 mid가 더 커야한다.(else는 반대로 mid가 작으면 된다.)

풀이

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

using namespace std;
int n, m;
int arr[100001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int l, r = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		r += arr[i];	// 최대값 r은 모든 배열의 합
	}
	l = *max_element(arr, arr + n);	// 최소값 l은 배열의 max값

	while (l <= r) {	
		int mid = (l + r) / 2;	// 현재 블루레이 길이

		int sum = 0, cnt = 0;	// mid일때 블루레이 수 구하기
		for (int i = 0; i < n; i++) {
			if (sum + arr[i] > mid) {
				sum = 0;
				cnt++;
			}
			sum += arr[i];
		}
		if (sum != 0) cnt++;	
		
        	// 블루레이 수와 m 비교하여 l,r값 조정하기 
		if (cnt > m) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
    
	cout << l;
	return 0;
}