백준 - 2343 기타 레슨 [이분탐색]

1. 2343 기타 레슨

1.1. 문제유형

• Binary Search

  1.2. 자료구조

• cnt (int) : 블루레이 개수
• file (int) : 레슨을 저장한 파일 크기
• mid (int) : 블루레이 크기
• left (int) : 가장 작은 블루레이 크기
• right (int) : 가장 큰 블루레이 크기

  1.3. 해결과정

• 가장 작은 블루레이 크기는 max(lesson), 최대 크기는 sum(lesson)이다.
• 주어진 m개의 블루레이에 강의를 저장하되, 블루레이 크기는 작을수록 좋다.
• 따라서 블루레이의 크기를 찾는 이분탐색 문제로 해결할 수 있다.

1. left는 max(lesson), right는 sum(lesson)로 설정한다.
2. left <= right일 동안 아래 과정을 반복한다.
3. 블루레이 크기를 중간값인 (left + right)//2로 지정한다.
4. 만약 파일 크기가 중간값을 넘어서면 cnt를 증가시키고 file에 영상을 저장한다.
5. 파일 크기가 아직 중간값보다 작다면 file에 영상을 더 추가한다.
6. 반복이 끝난 후 file에 영상이 남아있다면 cnt를 증가시킨다.
7. 최종 cnt가 m보다 크다면, 블루레이 크기가 작은 것이므로 left = mid+1
8. 최종 cnt가 m보다 작거나 같다면, 블루레이 크기가 큰 것이므로 answer에 중간값 저장 후 right = mid-1
9. 최종 answer를 출력한다.

n, m = map(int, input().split())
lesson = list(map(int, input().split()))
left, right = max(lesson), sum(lesson)
answer = left

while left <= right:
    cnt = 0
    file = 0
    mid = (left + right)//2

    for l in lesson:  
        if file+l > mid:
            cnt += 1
            file = l
        else:
            file += l
    if file:
        cnt+=1

    if cnt>m:
        left = mid+1
    else:
        answer = mid
        right = mid-1
print(answer)