[백준/알고리즘] 2343번 기타 레슨 (실버 1)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 2343번

 

기타 레슨들의 동영상 시간이 주어진다. 모든 레슨들을 블루레이 M개에 담아서 팔려고한다.
가능한 블루레이 크기 중 최소를 출력하시오.

 

풀이 알고리즘 : 이분탐색

 

문제의 조건에 "레슨의 순서가 바뀌면 안된다." 가 있으므로, 정렬은 하지 않는다.

 

정렬하지 않은 상태에서 이분탐색을 통해 블루레이의 크기를 기준으로 값을 좁혀나간다.

 

탐색 결과로 나온 블루레이의 개수가 M보다 많을경우 블루레이의 크기를 늘려주고,

그렇지 않은경우 블루레이의 크기를 줄여준다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

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

	int n, m;
	ll ans = (ll)(1e10);
	cin >> n >> m;
	ll arr[n] = {0};
	ll le = 1, ri = (ll)(1e12);
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
		if(le < arr[i]) le = arr[i];
	}
	le--;
	while(le <= ri) {
		// 이번 시행에서 블루레이의 크기
		ll mid = (le + ri) / 2;
		// 이번 시행에서 블루레이 개수, 현재까지 개수
		ll curcnt = 0, s = 0;
		// 이번 시행에서 최대합
		ll maxs = 0;

		// 앞에서부터 블루레이 개수 확인
		for(int i = 0; i < n; i++) {
			if(s + arr[i] <= mid) {
				s += arr[i];
			} else {
				// 더이상 강의를 담을 수 없을 때
				curcnt++;
				if(maxs < s) maxs = s;
				s = arr[i];
			}
		}

		// 남은게 있으면 다른 블루레이에 넣음
		if(0 < s) {
			curcnt++;
			if(maxs < s) maxs = s;
		}
		
		if(m < curcnt) {
			le = mid + 1;
		} else {
			if(maxs < ans) {
				ans = maxs;
			}
			ri = mid - 1;
		}
	}

	cout << ans;

	return 0;
}