[백준-2343] 기타 레슨 / Python

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

2343번: 기타 레슨

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를 늘려준다.