🖊️ 문제

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

---

🖊️ 생각

1. 아.. 진짜 뭔가 생각이 안났다.
   투포인터같긴 한데 장담은 못하겠고..그런느낌 ㅠ

결국 알고리즘 분류를 봤고,
이분탐색이라는 것을 확인.

그렇다면, 기준을 정해야 한다.
이분탐색을 돌릴 것은?

인덱스를 돌리자기엔,, 배열을 여러 개로 쪼개는 것이 목표이므로 XX

블루레이의 개수가 정해져 있고,
모두 같은 크기의 블루레이로 나눠야 하고,
블루레이의 가장 작은 크기를 구해야 한다.

예제처럼
1 2 3 4 5 6 7 8 9
이렇게 주어져도,
1 2 3 4 5 6 7 8 9 이렇게 나눠버릴 수도 있으니, 이 문제의 키포인트, 구해야 할 점은 블루레이의 길이

따라서, 이분탐색의 매개변수를 블루레이의 길이로 둔다.

최소 1개의 강의를 담아야 하므로, 블루레이의 길이가 될 수 있는 최솟값은 가장 큰 강의의 길이
또한, 최댓값은 모든 강의들의 합.

두 사이를 오가며, 최적의 해를 찾아간다.

,,
최소값을 구하므로, 블루레이의 길이를 줄일 때마다 출력값(값 == 블루레이의 최소 길이)을 저장해줘야 한다!

---

🖊️ 풀이

#include <iostream>
using namespace std;

int arr[100'001];
int n, m;

int GetBlueray(int size)
{
	int sum = 0;
	int result = 0;
	for (int i = 0; i < n; i++) {
		if (sum + arr[i] <= size)
			sum += arr[i];
		else {
			result++;
			sum = arr[i];
		}
	}
	if (sum > 0) result++;
	return result;
}

int main()
{
	cin >> n >> m;

	int total = 0;
	int maxValue = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		total += arr[i];
		maxValue = max(maxValue, arr[i]);
	}

	int left = maxValue;
	int right = total;
	int mid = 0;
	int answer = 0;
	while (left <= right) {
		mid = (left + right) / 2;
		int curCnt = GetBlueray(mid);
		if (curCnt <= m) {
			right = mid - 1;
			answer = mid;
		}
		else left = mid + 1;
	}
	cout << answer << endl;
}

---

🖊️ 고칠점

1. 이분탐색을 오랜만에 풀기도 했지만..
   매개변수 설정을 잘 고민해봐야 한다 수민아
2. 문제를 잘.. 읽고^^ 열심히 풀어야 한다 ^^
3. 최소값을 구하므로, 블루레이의 길이를 줄일 때마다 출력값(값 == 블루레이의 최소 길이)을 저장해줘야 한다!