🎸 백준 2343번: 기타 레슨 문제 정리 (이분 탐색 활용)

---

🧐 문제 해석

• N개의 강의가 있고, 각 강의는 특정 시간 길이를 가진다.
• 강의는 순서를 유지한 채로 M개의 블루레이에 나눠 담아야 한다.
• 각 블루레이에는 연속된 강의만 담을 수 있다.

🎯 목표:

M개의 블루레이에 나눠 담을 때, 가능한 블루레이 용량 중 최솟값을 구하라.

---

🔍 핵심 아이디어

이 문제는 **정답(최소 블루레이 크기)**를 이분 탐색으로 찾는 매개변수 탐색(Parametric Search) 문제이다.

✅ 이분 탐색 대상

• 블루레이 용량 (capacity)

• 범위:

  • start = max(lecture) → 강의를 딱 한개만 넣는 경우 가장 긴 길이의 비디오가 들어갈때 고려
  • end = sum(lecture) → 모든 강의를 한 블루레이에 넣는 경우

---

🧠 check(capacity) 함수 의미

def check(capacity):
    count = 1
    total = 0
    for lec in lecture:
        if total + lec > capacity:
            count += 1
            total = lec
        else:
            total += lec
    return count <= m

• 현재 블루레이 용량(capacity)으로 강의들을 m개 이하로 나눌 수 있는지를 확인한다.
• 강의를 순서대로 합쳐가며, 용량을 초과하면 블루레이 개수를 하나 추가한다.
• 마지막에 사용한 블루레이 수가 m개 이하라면 가능 → True

---

🔄 이분 탐색 구조

start = max(lecture)
end = sum(lecture)
result = end

while start <= end:
    mid = (start + end) // 2
    if check(mid):
        result = mid        # 정답 후보 저장
        end = mid - 1       # 더 작은 용량도 가능한지 확인
    else:
        start = mid + 1     # 너무 작음 → 더 큰 용량으로

print(result)

---

💯 정답

n, m = map(int, input().split())
lecture = list(map(int, input().split()))

def check(capacity):
    count = 1
    total = 0
    for lec in lecture:
        if total + lec > capacity:
            count += 1
            total = lec
        else:
            total += lec
    return count <= m

start = max(lecture)
end = sum(lecture)
result = end

while start <= end:
    mid = (start + end) // 2
    if check(mid):
        result = mid
        end = mid - 1
    else:
        start = mid + 1

print(result)

---

💭 시도

def add_video(capacity,what_video,step):
    if step == m+1 :
        max_size = max(max_size,capacity)
        return
    count = 0
    sum_video = 0
    while True :
        if sum_video + lecture[count+what_video+1] > avg_size :
            add_video(sum_video+lecture[count+what_video+1],what_video+count+1,step+1)
            add_video(sum_video,what_video+count,step+1)
        else :
            sum_video += lecture[count+what_video]

✅ 각 블루레이에 들어갈 원소의 합이 비슷해야 최적 결과라고 생각함

• 즉, 합이 평균에 가까워야 함

✅ "최대값 포함 여부가 핵심"

• 평균에 가까워 졌을때 포함하냐 안포함하냐로 탐색할까?
• ❌완전탐색에 가까워서 시간초과 메모리초과 또는 재귀 깊이 문제도 생길 수 있다 생각..

✅ "1654랑 비슷한 느낌"

✅ 결론 한 줄

이 문제는 "블루레이 용량"이라는 정답 후보를 잡고, 그 값이 가능한지를 검사해나가는 매개변수 이분 탐색 문제다! 🎯

---

🔑 자꾸 놓치는 이분탐색의 역할

• 이분 탐색은 정답 범위를 줄여가는 도구