boj.kr/2343 기타 레슨 (silver1) 파이썬 풀이

1. lo를 0, hi를 기타 레슨 시간 목록 lectures의 총합으로 초기화한다.

2. 출력할 변수 ans에는 hi를 저장한다.

3. lo가 hi이하이면 아래 4-9를 반복한다.

4. mid에 (lo+hi)//2를 저장한다.

5. mid가 lectures 요소 중 최대값보다 작으면, lo를 mid+1으로 저장하고 다음 반복으로 넘어간다.

6. sub를 0, sub_cnt를 1으로 초기화하고 lectures를 순회하면서 아래 6.1-6.2를 반복한다.

6.1. sub에 lectures의 요소를 더한 값이 mid 이하이면 sub에 lectures의 요소를 더한다.

6.2. 만약 mid보다 크다면 sub_cnt에 1을 더하고 sub에는 lectures의 요소를 저장한다.

7. sub_cnt가 M(블루레이의 개수) 이하이면 ans에 ans와 mid 중 더 작은 값을 저장한다.

8. hi를 mid-1으로 갱신한다.

9. sub_cnt가 M보다 크면 lo에 mid+1으로 갱신한다.

10. ans를 출력한다.

 

N, M = map(int, input().split())
lectures = list(map(int, input().split()))

lo = 0
hi = sum(lectures)
ans = hi

while lo <= hi:
    mid = (lo+hi)//2

    if mid < max(lectures):
        lo = mid + 1
        continue

    sub = 0
    sub_cnt = 1
    for i in range(len(lectures)):
        if (sub + lectures[i]) <= mid:
            sub += lectures[i]
        else:
            sub_cnt += 1
            sub = lectures[i]
    if sub_cnt <= M:
        ans = min(ans, mid)
        hi = mid-1
    else:
        lo = mid+1

print(ans)

 

하나의 블루레이에 최소 한개의 강의를 담아야 하므로 가장 긴 강의시간을 담을 수 없는 경우에는 lo를 mid+1으로 갱신해야 한다.

블루레이 크기 중 최소를 구해야 하므로 매번 최소비교를 해주어야 한다.