문제

[백준] 기타레슨

접근방법

레이블 하나 용량의 최소값은 강의 길이 중 가장 긴 것이다

low = max val in arr

레이블 하나 용량의 최대값은 모든 강의 길이를 합친 것이다

high = sum all arr element

문제에서 요구하는 최소값은 low와 high 사이에 있다

mid = (low + high)/2

이분탐색으로 이 문제의 영역을 줄이는 방법

mid의 용량이 각 레이블에 영상을 차례로 담고 제공하는 레이블 갯수와 동일한가

if(tempSum > mid) cnt ++
cnt == givenCount?

계산된 cnt가 더 크다면 용량을 너무 작게 잡은 것
low를 증가시킨다

low = mid + 1

계산된 cnt가 더 작다면 용량을 너무 크게 잡은 것
high를 증가시킨다

high = mid - 1

어려웠던 것

스스로 정답을 내지 못했다

무엇을 탐색할 것인가

이분탐색 몇 문제를 풀며 이분탐색으로 무엇을 찾을 것인가란 문제가 중요하다는 것을 알았다
이 분이 풀었던 방법이 좋았던 것
최소값을 이분탐색해 가며 해당 최소용량에 모든 데이터가 들어가냐를 판별
최소용량을 설정한 것과 답인지 아닌지 판별하는 것

내 문제 풀이의 문제점

내가 풀었을 때는 낮은 수부터 총합/레이블갯수를 최소값으로 설정하여 다음 것을 넣어 다시 판별하는 식으로 풀었는데 예외가 있어서 오류가 났을 것 같다
더군다나 코드를 적으면서도 이것이 맞는 것인지 아닌지에 대한 판별도 되지 않았다

앞으론 조금 더 논리적으로 맞을 때까지 방법을 생각하고 코드를 짜기 시작해야 할 것 같다

• 참고한 코드

해결

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

typedef long long ll;

using namespace std;

ll arr[100001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N, M; // N : 레슨수, M : 블루레이의 갯수
	cin >> N >> M;

	ll sum = 0, low = -1;

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		sum += arr[i]; // 모든 레슨의 길이를 더하 것은 high가 되고
		low = max(low, arr[i]); // 각 레슨 중 가장 긴 것은 low가 된다
	}

	ll high = sum;

	while (low <= high) {
		ll cnt = 0, tempSum = 0; // cnt : 계산되는 블루레이의 수 // tempSum : 각 블루레이에 들어가는 영상길이의 합
		ll mid = (low + high) / 2;

		for (int i = 0; i < N; i++) // 반복문을 써서 계산이 많을 것 같지만 시간복잡도는 aN이다
		{
			if (tempSum + arr[i] > mid) { // 현재 레이블에 생각한 최소값을 넘어가면 다음 레이블에 저장하는 식
				tempSum = 0;
				cnt += 1;
			}
			tempSum += arr[i]; // 레이블에 영상저장
		}
		if(tempSum != 0) cnt += 1; // 블루레이의 크기가 가정한 크기보다 작아서 1 증가 못시키면 1더함

		if (cnt <= M) { // 생성되는 레이블 갯수가 모자르다면 high 값줄임
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	cout << low;
	return 0;
}
//ref : https://chanhuiseok.github.io/posts/baek-22/