백준 2343번 - 기타 레슨 (Python)

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

2343번: 기타 레슨

생각해보기

M개의 블루레이를 기준으로 블루레이의 최소 크기를 찾는 이분탐색 문제이다.

 

각 강의의 길이는 오름차순으로 정렬되어 있지 않고, 순서가 변경되어선 안된다.

따라서 start는 배열의 max, end는 배열의 합으로 정한다.

 

처음에는 각 블루레이의 크기를 배열에 저장했으나 이는 불필요한 연산이었을 뿐 아니라, 연산을 끝까지 했을 때 올바른 결과를 저장하고 있지 않았다.

 

블루레이의 개수인 cnt를 1로 초기화함으로써 연산 과정에서 블루레이의 개수를 맞춰줄 수 있다.

또한, 용량을 초과했을 때 다음 블루레이에 저장하기 위해 해당 강의를 res에 저장한다.

 

풀이)

import sys

input = sys.stdin.readline

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

# 강의 길이는 정렬되어 있지 않음
start = max(arr)
end = sum(arr)
# ans = 10e9

while (start <= end):
    mid = (start + end) // 2
    res = 0
    # cnt를 1로 시작하여 블루레이의 개수 맞춰주기
    cnt = 1

    # 블루레이에 영상을 담을 수 없는 경우
    if (max(arr) > mid):
        start = mid + 1
        continue

    # for-loop를 함수로 따로 뺐을 때, 더 빠름
    for e in arr:
        if ((res + e) <= mid):
            res += e
        else:
            cnt += 1
            # 다음 루프를 돌 때 해당 블루레이에 저장 가능
            res = e

    if ((cnt) > M):
        start = mid + 1
    else:
        end = mid - 1
        # ans = min(ans, mid)

print(start)
# print(ans)