백준 2343 : 기타레슨 파이썬(python)

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

2343번: 기타 레슨

 

# 블루레이에는 총 N개의 강의
# i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화
# M개의 블루레이는 모두 같은 크기

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

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    temp = 0
    for i in range(n):
        if temp + data[i] > mid:
            cnt += 1
            temp = 0
        temp += data[i]

    cnt += 1 if temp else 0

    if cnt <= m:
        right = mid - 1
    else:
        left = mid + 1

print(left)

 

블루레이의 최대 길이는 리스트의 합, 최소 길이는 리스트의 최댓값이다.

리스트에 1 ~ 9까지 저장되어있다면 각각 최대, 최소 길이는 45와 9가 된다.

이 때 블루레이에 들어갈 수 있는 레슨은 1개, 9개가 될 수 있다.

 

위에서 언급한 대로 left와 right를 설정해주고 반복문을 통해 얻어진 리스트의 합이 mid보다 커지면 cnt(블루레이 개수)를 1씩 증가시킨다. 이렇게 얻은 블루레이 개수가 m보다 작으면 right를 줄여주고, m보다 크다면 left를 늘려준다.