BOJ 2343번: 기타 레슨

www.acmicpc.net/problem/2343

2343번: 기타 레슨

아이디어:

블루레이 크기를 이분 탐색. high = 10^9, low = 1

레슨의 길이를 더하다가 mid보다 같거나 커지면 블루레이 개수 +1

레슨의 길이가 M보다 크면 low = mid + 1, 같거나 작으면 블루레이 크기를 더 줄여야 하니까 high = mid - 1하고 ans 업데이트

 

import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

high = 10**9
low = 1
ans = high

while (high>=low):
    mid = (high+low)//2
    num = 0
    time = 0
    for i in arr:
        if (i>mid): #블루투스의 크기가 레슨의 길이보다 작은 경우
            num = m+1 #low = mid + 1이 되도록
            break
        time+=i #레슨의 길이 더하기
        if (time>mid): #mid보다 커지면 자르기
            num+=1
            time = i
        elif (time==mid):
            num+=1
            time = 0

    if (time<mid and time!=0):
        num+=1 #마지막에 남는 부분
       
    if (num>m):
        low = mid + 1
    elif (num<=m):
        high = mid - 1
        ans = min(ans, mid) #자른 부분의 개수가 m보다 작으면 답 업데이트
print(ans)

※ ans = min(ans, mid) -> 이분탐색이라 그런건지 숫자가 왔다갔다 해서 최솟값으로 갱신해야 하더라

※ num==m일때만 값을 갱신하니 틀렸다. num<m 이면 더 잘게 쪼갤 수 있다는 말이니까 포함해야 한다. 그런 경우도 가능하더라고..

7 7
5 9 6 8 7 7 5

답: 9 

--> 이런 경우..