[백준] 2343. 기타 레슨

문제

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

2343번: 기타 레슨

 

설계

- 이분탐색

- 백준 문제 설명에 띄어쓰기가 헷갈리게 되어있어 문제를 이해하는데 오래 걸렸다.

- SumV에 남아있는 것을 하나의 묶음으로 처리하는 것이 Point

N, M = map(int, input().split())
arr = list(map(int, input().split()))
# start : 블루레이 중 가장 큰값이 최소값이어야 모두 담을 수 있다.
start, end = max(arr), sum(arr)

switch = 1
while switch:
    mid = (start + end) // 2
    cnt = 0     # 블루레이의 개수
    sumV = 0    # 블루레이의 합

    for i in arr:
        if sumV + i > mid:      # 다음 합계가 mid보다 큰지 확인
            sumV = 0
            cnt += 1
        sumV += i
    if sumV:        # sumV에 무언가 남아 있으면 하나의 개수로 처리
        cnt += 1

    if start > end:     # 종료 조건
        switch = 0

    if cnt > M:
        start = mid + 1
    else:
        end = mid - 1

print(start)