[Python | 2343] 기타 레슨

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

---

문제 설명

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

 

📌 시간 제한: 2초

---

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

---

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

---

문제 접근

입력으로는 n개의 강의 길이와 m개의 블루레이 개수가 주어진다. 각 강의는 순서를 바꿀 수 없고, 쪼개서 담을 수도 없다. 또한 블루레이에는 연속된 강의만 담을 수 있으며, 블루레이 크기 중 최댓값을 최소화하는 것이 목표다.

즉, 문제는 강의들을 m개의 묶음으로 나누되, 각 묶음의 합 중 최댓값을 최소화하는 최적화 문제다.

여기서 핵심은, 특정 블루레이 크기를 기준으로 조건을 만족할 수 있는지 판단할 수 있다는 점이다. 이처럼 조건을 만족하는지의 여부를 기준으로 정답을 좁혀갈 수 있기 때문에, 이 문제는 이분 탐색(Parametric Search) 으로 해결할 수 있다.

 

❓ 이건 왜 Parametric Search인가?

이 문제는 이분 탐색을 쓰지만, 일반적인 Binary Search 와는 다르다.
바이너리 서치는 정렬된 배열에서 원하는 값을 직접 찾는 것이 목적이다.
반면 이 문제는, 특정 블루레이 크기 mid를 기준으로 조건을 만족하는지 확인한 뒤, 그 중에서 가능한 최소 크기를 찾아야 한다.

즉, 가능/불가능 여부를 기준으로 정답 범위를 좁혀가며 최적의 해를 찾는 과정이 필요하다.
이런 탐색을 Parametric Search 라고 부른다.

 

예시 비교:

Binary Search	5라는 숫자가 배열에 있는가?	값을 직접 찾음
Parametric Search	블루레이 크기를 100으로 했을 때 가능한가? 가능하다면 더 줄일 수 있을까?	조건을 만족하는 최적의 값 탐색

 

이 문제에서 탐색 대상은 값 그 자체가 아니라, 조건(m개 이하의 블루레이로 분배 가능)을 만족하는 최소한의 크기 값이기에 파라메트릭 서치 문제다.

 

💡 이분 탐색 적용 방식

• 탐색 대상은 블루레이 하나의 크기
• 어떤 크기 mid가 주어졌을 때, 이 크기로 모든 강의를 분배할 수 있는지를 시뮬레이션
• 필요한 블루레이 개수가 m보다 작거나 같다면 → 크기를 더 줄여볼 수 있다
• 필요한 개수가 m보다 많다면 → 크기를 늘려야 한다

탐색 범위 설정:

• lo = max(lectures)
  → 가장 긴 강의는 반드시 하나의 블루레이에 들어가야 하므로, 이것보다 작은 값은 불가능
• hi = sum(lectures)
  → 모든 강의를 하나의 블루레이에 몰아 담을 경우의 최대 크기

---

구현

lo = max(lectures)      # 블루레이 최소 크기 (가장 긴 강의는 반드시 담겨야 함)
hi = sum(lectures)      # 블루레이 최대 크기 (전체를 하나에 담는 경우)
answer = hi

while lo <= hi:
    mid = (lo + hi) // 2
    cnt = 1     # 필요한 블루레이 개수
    total = 0   # 현재 블루레이에 담긴 총 길이

    for length in lectures:
        if total + length > mid:
            cnt += 1        # 새 블루레이 시작
            total = length  # 현재 강의부터 다시 담기 시작
        else:
            total += length

    if cnt <= m:
        answer = mid        # 블루레이 개수 조건을 만족 → 크기 줄여보기
        hi = mid - 1
    else:
        lo = mid + 1        # 블루레이 개수 초과 → 크기 키워야 함