백준: 2343 기타 레슨

문제

2343번: 기타 레슨

 

문제 풀이

 블루레이에 N개의 레슨이 들어가는데, 블루레이를 녹화할 때는 레슨의 순서가 바뀌면 안 되고 M개의 블루레이에 플레이 타임이 모두 같도록 해서 만들어야 한다. 이때 가능한 블루레이의 크기 중 최소를 출력하는 문제이다. 이 문제는 전형적인 이분 탐색 문제이다.

 

• start, end를 `max(lesson)`, `sum(lesson)`로 설정한다.
  • 하나의 레슨을 담고자 한다면 최소 lesson에서 가장 큰 값은 되어야 한다.
  • 하나의 블루레이에 모든 레슨을 담고자 한다면 모든 레슨 시간을 합친 것과 같아야 한다.
• 이분 탐색을 통해, 블루 레이의 레슨 시간을 변경하며 탐색을 진행한다.

 

코드

if __name__ == '__main__':
    n, m = map(int, input().split())
    lesson = list(map(int, input().split()))
    start, end = max(lesson), sum(lesson)

    while start <= end:
        mid = (start + end) // 2

        cnt = 0
        play_time = 0
        for l in lesson:
            # play_time이 m보다 커지면 새로운 dvd 필요
            if play_time + l > mid:
                cnt += 1
                play_time = 0

            play_time += l

        cnt += 1 if play_time else 0

        if cnt <= m:
            end = mid - 1
        else:
            start = mid + 1
    print(start)