백준 2343번 기타 레슨 C++

---

백준 2343번 기타 레슨 C++

---

문제설명

🔹 문제

강토는 자신의 기타 강의 영상을 블루레이에 담아 판매하려고 합니다. 총 N개의 강의가 있으며, 이 강의들을 M개의 블루레이에 나눠서 담으려 합니다.

중요 조건은 다음과 같습니다:

• 강의의 순서를 바꿀 수 없습니다. (선형 순서 유지)
• 한 블루레이에는 연속된 강의들만 들어가야 합니다.
• 모든 블루레이는 동일한 크기여야 합니다.
• M개의 블루레이에 모두 담되, 블루레이 크기는 최소가 되도록 해야 합니다.

🔹 입력 형식

• 첫째 줄: `N` (강의 수), `M` (블루레이 수)
  (`1 ≤ N ≤ 100,000`, `1 ≤ M ≤ N`)
• 둘째 줄: 각 강의의 길이 (분 단위, 자연수, 최대 10,000)

🔹 출력 형식

• 가능한 블루레이 크기 중 최소값을 출력합니다.

🔹 테스트케이스

예제 입력 1

9 3
1 2 3 4 5 6 7 8 9

예제 출력 1

17

---

설명

예를 들어 강의 길이가 다음과 같습니다.

1 2 3 4 5 6 7 8 9

총 9개의 강의입니다. 이 강의들을 3개의 블루레이에 나누어 담아야 합니다.

블루레이는 다음과 같은 조건을 가집니다:

• 모든 블루레이는 같은 크기여야 합니다.
• 한 블루레이에는 연속된 강의들만 들어갈 수 있습니다.
• 강의 순서는 바꿀 수 없습니다.

이 조건을 만족하면서, 각 블루레이의 용량(최대 담을 수 있는 총합)을 가능한 한 작게 만들어야 합니다.

예를 들어, 블루레이 크기를 17로 정하면 다음과 같이 나눌 수 있습니다.

[1 2 3 4 5 2] → 합: 17 이하  
[6 7]         → 합: 13  
[8 9]         → 합: 17

총 3개의 블루레이에 담을 수 있고, 각 블루레이 크기가 모두 17 이하이므로 조건을 만족합니다.

이보다 더 작은 크기로도 3개에 담을 수 있는지 확인하며, 가능한 블루레이 크기 중 가장 작은 값을 찾아야 합니다.

---

아이디어

이분탐색의 전제조건: 정렬

• 이분 탐색을 하려면 값들이 정렬된 상태여야 합니다.
• 예를 들면 다음과 같이 정렬된 수가 있다고 가정합니다.

1, 2, 3, 4, 5, 6, 7

• 이 배열에서 찾고자 하는 값이 3이라고 가정합니다.
• 이때 중간값은 4입니다.

1, 2, 3, {4}, 5, 6, 7

• 우리가 찾는 값인 3은 중간값 4보다 작기 때문에
• 이제 탐색 범위는 다음과 같이 줄어듭니다.

1, 2, 3

• 여기서 다시 중간값은 2입니다.

1, {2}, 3

• 찾고자 하는 값 3은 2보다 크므로
• 이제 탐색 범위는 다음과 같이 줄어듭니다.

3

• 이처럼 이분 탐색은 항상 정렬된 배열에서 중간값을 기준으로 직접적인 수치를 기반으로 탐색 범위를 줄여가며 찾고자 하는 값을 좁혀가는 방식입니다.
• 따라서 이 문제에서도 가능한 블루레이 크기들을 정렬된 수의 집합으로 생각할 수 있으므로 이분 탐색이 가능합니다.

---

이진 탐색 진행 과정

현재 탐색 배열입니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45

• 시작값은 9입니다.
• 끝값은 45입니다.
• 중간값은 (9 + 45) / 2 = 27입니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, {27}, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45

블루레이 용량을 27로 설정합니다. 강의 배열은 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 구합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15
• 15 + 6 = 21
• 21 + 7 = 28 → 27을 초과하므로 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 + 5 + 6 = 21

7부터 다시 시작합니다.

• 7 + 8 = 15
• 15 + 9 = 24 → 가능
  → 두 번째 블루레이: 7 + 8 + 9 = 24

총 블루레이 개수는 2개입니다.

2개는 우리가 사용할 수 있는 최대 블루레이 수인 3개 이하이므로, 27이라는 용량으로 강의를 나눌 수 있습니다. 더 작은 용량으로도 가능할 수 있으므로 탐색 범위를 줄입니다.

---

이제 새로운 탐색 배열은 다음과 같습니다.

9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26

• 시작값은 9입니다.
• 끝값은 26입니다.
• 중간값은 (9 + 26) / 2 = 17입니다.

9, 10, 11, 12, 13, 14, 15, 16, {17}, 18, 19, 20, 21, 22, 23, 24, 25, 26

블루레이 용량을 17로 설정합니다. 강의 배열은 그대로입니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 구합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15
• 15 + 6 = 21 → 17 초과 → 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 + 5 = 15

6부터 다시 시작합니다.

• 6 + 7 = 13
• 13 + 8 = 21 → 17 초과 → 블루레이 2개 완성
  → 두 번째 블루레이: 6 + 7 = 13

8부터 다시 시작합니다.

• 8 + 9 = 17 → 가능
  → 세 번째 블루레이: 8 + 9 = 17

총 블루레이 개수는 3개입니다. 3개는 조건을 만족합니다. 더 작은 용량으로도 가능할 수 있으므로 탐색 범위를 더 줄입니다.

---

현재 탐색 배열입니다.

9, 10, 11, 12, 13, 14, 15, 16

• 시작값은 9입니다.
• 끝값은 16입니다.
• 중간값은 (9 + 16) / 2 = 12입니다.

9, 10, 11, {12}, 13, 14, 15, 16

블루레이 용량을 12로 설정합니다.

강의 배열은 다음과 같습니다.

1, 2, 3, 4, 5, 6, 7, 8, 9

1부터 누적합을 계산합니다.

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15 → 12 초과 → 블루레이 1개 완성
  → 첫 번째 블루레이: 1 + 2 + 3 + 4 = 10

5부터 다시 시작합니다.

• 5 + 6 = 11
• 11 + 7 = 18 → 12 초과 → 블루레이 2개 완성
  → 두 번째 블루레이: 5 + 6 = 11

7부터 다시 시작합니다.

• 7 + 8 = 15 → 12 초과 → 블루레이 3개 완성
  → 세 번째 블루레이: 7

8부터 다시 시작합니다.

• 8 + 9 = 17 → 12 초과 → 블루레이 4개 완성
  → 네 번째 블루레이: 8

9만 남음
→ 다섯 번째 블루레이: 9

총 블루레이 개수는 5개입니다.

조건은 3개 이하이므로 12는 너무 작습니다.

→ 탐색 범위를 더 큰 값으로 좁혀야 합니다.

---

새로운 탐색 배열은 다음과 같습니다.

13, 14, 15, 16

중간값은 (13 + 16) / 2 = 14입니다.

13, {14}, 15, 16

블루레이 용량을 14로 설정합니다.

강의 배열:

1, 2, 3, 4, 5, 6, 7, 8, 9

누적합 계산:

• 1 + 2 = 3
• 3 + 3 = 6
• 6 + 4 = 10
• 10 + 5 = 15 → 초과 → 블루레이 1
  → 블루레이 1: 1 + 2 + 3 + 4 = 10

5부터:

• 5 + 6 = 11
• 11 + 7 = 18 → 초과 → 블루레이 2
  → 블루레이 2: 5 + 6 = 11

7부터:

• 7 + 8 = 15 → 초과 → 블루레이 3
  → 블루레이 3: 7

8부터:

• 8 + 9 = 17 → 초과 → 블루레이 4
  → 블루레이 4: 8

9만 남음
→ 블루레이 5: 9

총 블루레이 개수는 5개입니다. 조건 초과입니다.

14는 여전히 작습니다. → 탐색 범위를 더 크게 합니다.

---

다음 탐색 배열은:

15, 16

중간값은 (15 + 16) / 2 = 15입니다.

{15}, 16

블루레이 용량을 15로 설정합니다. 계산 반복합니다.

• 블루레이 1: 1 + 2 + 3 + 4 = 10
• 블루레이 2: 5 + 6 = 11
• 블루레이 3: 7 + 8 = 15
• 블루레이 4: 9

총 블루레이 개수: 4
조건 초과 → 15는 부족합니다. → 다음 탐색 배열은

16

중간값 16 → 직접 판단

• 블루레이 1: 1 + 2 + 3 + 4 = 10
• 블루레이 2: 5 + 6 = 11
• 블루레이 3: 7
• 블루레이 4: 8
• 블루레이 5: 9

→ 총 5개 → 초과
→ 16도 불가능

---
다시 이전 단계로 돌아가겠습니다. 이미 17에서는 가능했기 때문에 최소 가능한 값은 17입니다.

최종 정답은 17입니다.

---

left와 right가 역전되는 순간

이전 탐색 흐름은 다음과 같습니다.

• 탐색 배열:

[9, 10, 11, ..., 15, 16, 17, 18, ..., 45]

• 중간값 `mid = 27` → 가능
  → 탐색 범위 줄임: `right = 26`
• `mid = 17` → 가능
  → `right = 16`
• `mid = 12`, `14`, `15`, `16` → 불가능
  → `left = 17`
  → 마지막 상태:

left = 17  
right = 16  

이 시점에서 left > right입니다. 이 순간이 바로 탐색 종료 조건입니다.

---

왜 이 순간 left가 정답인가?

1. right는 실패한 값들의 마지막 지점입니다.

• right가 16이라는 것은, 용량이 16일 때 강의를 3개 이하로 나눌 수 없다는 것을 의미합니다.
• 그보다 작은 값들 (`15, 14, ... 9`)도 모두 실패였습니다.
• 따라서 16 이하는 모두 불가능한 값의 영역입니다.

2. left는 성공했던 영역의 가장 첫 지점입니다.

• left가 17이라는 것은, 용량이 17일 때 강의를 정확히 3개로 나눌 수 있었다는 의미입니다.
• 그보다 큰 값들도 모두 가능하지만, 우리는 가장 작은 가능한 값을 찾고 있기 때문에 이 시점에서 left는 최소 가능한 값입니다.

---

시각화로 정리

탐색 전 배열:

[9, 10, 11, ..., 15, 16, 17, 18, ..., 45]

이진 탐색 후 실패 영역:

❌ 9, 10, 11, 12, 13, 14, 15, 16  

성공 영역:

✅ 17, 18, 19, ..., 45

결정 순간:

left → 17  
right → 16  

→ 역전 발생 → 탐색 종료
→ left = 17이 최소 정답으로 확정됩니다.

---

아이디어 요약

• 이분 탐색에서 `left > right`가 되는 순간은 최소값을 찾는 문제에서의 정답 확정 순간입니다.
• 그 이유는 left는 가능한 영역의 경계선이며, 그 앞은 모두 실패했기 때문입니다.
• 따라서 left는 처음으로 조건을 만족한 값이 되며, 이 값이 바로 우리가 찾는 최소 블루레이 용량입니다.

---

✅ 전체코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(void)
{
	int N, M, sum_1 = 0;
	cin >> N >> M;

	int* arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
		sum_1 += arr[i];
	}
	int* min_el = max_element(arr, arr + N);
	int left = *min_el;
	int right = sum_1;
	int mid, answer = 0;

	while (left <= right)
	{
		mid = (left + right) / 2;

		int k = 1;
		sum_1 = 0;
		for (int i = 0; i < N; i++)
		{
			if (arr[i] + sum_1 <= mid)
				sum_1 += arr[i];
			else
			{
				sum_1 = arr[i];
				k++;
			}
		}

		if (k <= M)
		{
			right = mid - 1;
			answer = mid;
		}
		else
		{
			left = mid + 1;
		}
	}

	cout << answer << endl;
	delete[] arr;
	return 0;
}

---

✅ 개별코드 ①: `while (left <= right)` 조건

🔷 코드

while (left <= right)

🔷 왜 `<`가 아니라 `<=`인지 설명

• 이진 탐색은 항상 탐색 범위가 정답을 포함하고 있다는 보장을 유지해야 합니다.
• 만약 `left == right`일 때 반복을 멈춘다면, 마지막으로 남은 하나의 경우를 확인하지 않고 종료하게 됩니다.

---

💡 사례 기반 설명

arr = {3, 3, 3, 3, 3}   // 총합: 15
M = 3
left = max_element = 3
right = 15

탐색이 아래와 같이 진행됩니다.

1. mid = (3+15)/2 = 9
   → 가능 (3+3+3, 3+3) → 2개
   → right = 8, answer = 9
2. mid = (3+8)/2 = 5
   → 3개 필요 → 가능
   → right = 4, answer = 5
3. mid = (3+4)/2 = 3
   → 정확히 5개의 블루레이 필요 → 불가능
   → left = 4
4. mid = (4+4)/2 = 4
   → 4개의 블루레이 필요 → 불가능
   → left = 5

이 시점에서:

left = 5, right = 4 → 종료

→ 정답은 `answer = 5`로 안전하게 저장됩니다.

🟡 하지만 만약 조건이 `left < right`였다면?
→ mid = 4 계산 전에 종료되므로
→ 정답 `5`를 확인하지 못하게 됩니다.

---

✅ 개별코드 ②: 블루레이 분리 조건 처리

🔷 코드

for (int i = 0; i < N; i++)
{
	if (arr[i] + sum_1 <= mid)
		sum_1 += arr[i];
	else
	{
		sum_1 = arr[i];
		k++;
	}
}

🔷 설명

• `sum_1`은 현재 블루레이에 담고 있는 강의들의 합입니다.
• `arr[i] + sum_1`이 `mid`보다 크면,
  → 그 강의는 현재 블루레이에 담을 수 없습니다.
  → 블루레이 하나를 새로 추가하고 `sum_1 = arr[i]`로 시작합니다.

---

💡 오류났던 부분 요약

• 예전에는 `sum_1 = 0;`만 하고 `arr[i]`를 새로 더하는 코드를 빠뜨렸습니다.
  → 그럼 현재 강의가 완전히 무시되는 오류가 발생합니다.

---

💡 사례 기반 설명

arr = {6, 3, 2, 5}
mid = 8

• 블루레이 1: 6 + 3 = 9 → 초과 → 실패
• 올바른 방식:
  1. sum = 6
  2. 6 + 3 = 9 > 8 → 블루레이 끊음, k = 2
  3. sum = 3
  4. 3 + 2 = 5 → OK
  5. 5 + 5 = 10 > 8 → 블루레이 끊음, k = 3
  6. sum = 5

정확히 끊어주는 기준은 `sum_1 + arr[i] > mid`일 때 새 블루레이를 시작하는 것입니다.

---

✅ 개별코드 ③: `answer = mid` 저장 이유

🔷 코드

if (k <= M)
{
	right = mid - 1;
	answer = mid;
}

🔷 설명

• `mid`는 현재 가능한 블루레이 크기입니다.
• 이 크기로 M개 이하로 나눌 수 있다는 것은 조건 만족입니다.
• 하지만 목표는 최소 크기를 찾는 것이므로
  → `mid`보다 더 작은 값도 가능한지 확인해야 합니다.

그래서

• `answer = mid;`로 조건을 만족한 값은 저장해두고
• `right = mid - 1`로 더 작은 범위를 확인합니다.

---

💡 사례 기반 설명

arr = {5, 5, 5}
M = 3
left = 5, right = 15

• mid = 10 → 가능 → answer = 10
• mid = 7 → 가능 → answer = 7
• mid = 6 → 가능 → answer = 6
• mid = 5 → 가능 → answer = 5
• mid = 4 → 불가능 → left = 5 → 종료

마지막 가능한 `mid = 5`는 저장해두지 않으면 사라지게 됩니다.

---

🔚 결론 요약

개별코드 구간	왜 필요한가?	사례로 본 핵심
`while (left <= right)`	마지막 남은 범위 확인	`left == right`일 때가 정답일 수 있음
`arr[i] + sum_1 > mid` 기준으로 끊기	블루레이 개수 정확히 계산	넘치는 순간 끊고 sum 초기화
`answer = mid` 저장	가능한 값이더라도 더 작은 값 찾기 위해 필요	최솟값 갱신용 변수