[테스트케이스 추가] 백준 2343: 기타 레슨 python, 파이썬

1. 문제

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

2343번: 기타 레슨

 

 

2. 풀이

binary search

 

 

3. 구현

import sys
import math

# sys.stdin = open('input.txt')
n,m = map(int, sys.stdin.readline().split())
tmp = sys.stdin.readline().split()
lis=[]
for item in tmp:
    lis.append(int(item))
# lis = sorted(lis)

def cnt_video(size):
    cnt=0
    tmp_sum=0
    for item in lis:
        if tmp_sum+item>size:
            cnt+=1
            tmp_sum=0
        tmp_sum+=item
    return cnt+1

le = max(lis)
ri = sum(lis)

while le<=ri:
    mid=(le+ri)//2
    cnt=cnt_video(mid)
    if cnt<=m:
        ri=mid-1
    else:
        le=mid+1

print(le)

 

 

4. 테스트케이스 추가

12 3
10 8 7 2 8 9 4 12 7 5 2 9

답: 33

 

12 5
7 3 3 10 4 8 7 9 2 2 12 2

답: 15