(파이썬) 백준 2343번 "기타 레슨"

---

# 답

N, M = map(int, input().split())
lessons = list(map(int, input().split()))
l = max(lessons)
r = sum(lessons)
m = (l + r) // 2
ans = r

def is_possible(sz):
    cnt = 1
    bluray = 0
    for lesson in lessons:
        if bluray + lesson <= sz:
            bluray += lesson
        else:
            cnt += 1
            bluray = lesson

    return cnt <= M

while l <= r:
    if is_possible(m):
        ans = m
        r = m - 1
    else:
        l = m + 1

    m = (l + r) // 2

print(ans)

 

 

 

 

---

# 분석

파라메트릭 서치를 이용하여 푸는 문제입니다.

주어진 강의들을 M개로 쪼개는 가능한 모든 조합들을 완전 탐색하며 푸는 방법을 가장 쉽게 떠올릴 수 있습니다. 하지만 이 문제는 완전탐색으로 풀 경우 구현도 꽤 복잡해질 뿐더러 시간 초과가 날 것으로 예상됩니다.

 

이 문제는 정답이 될 수 있는 후보군들의 최솟값(가장 긴 강의 시간)과 최댓값(모든 강의 시간의 합)을 알 수 있으므로, 최솟값과 최댓값 사이에서 이분탐색을 해 나가는 풀이가 가장 이상적입니다.

 

★ 정답의 최솟값과 최댓값을 알 수 있는지 판단해보고, 알 수 있다면 파라메트릭 서치 풀이법을 고려해보자!

(파이썬) 알고리즘 유형 5. 이분 탐색