[boj] 백준 2343 기타 레슨 python 풀이

문제

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

2343번: 기타 레슨

 

문제 풀이

이분탐색으로 찾을 값 : 블루레이의 길이

블루레이의 길이를 바꿔가며 그 길이로 나눴을 때

group의 수가 M개 초과면 블루레이 길이를 더 길게

M개 이하면 블루레이 길이를 더 작게

 

코드

import sys
input = sys.stdin.readline
import bisect

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

def count(video_list, video_leng):
    cnt = 1
    tmp = 0

    for i in range(len(video_list)):
        if tmp + video_list[i] > video_leng:
            tmp = 0
            cnt += 1
        tmp += video_list[i]
        
    return cnt

# 블루레이의 크기를 탐색
def binary_search(LIST):
    s = max(video_list) # 블루레이 크기가 최소한 max(video_list)는 되야 group이 나눠짐
    e = sum(video_list) # 블루레이 크기가 sum(video_list)면 group이 한 덩어리로 나뉨
    res = 0

    while s<=e:
        mid = (s+e)//2

        video_cnt = count(video_list,mid) # mid(블루레이 크기)에 따른 group 수
        if video_cnt > M: 
            s = mid + 1
        else:
            e = mid - 1
            res = mid

    return res

print(binary_search(video_list))