[백준] 2343번:기타 레슨 (Python 파이썬)

문제

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

2343번: 기타 레슨

 

풀이 및 소스코드

 

여기서 한가지 자칫 실수할 것이

7 6
100 400 300 100 500 101 400

답: 500

이 반례이다.

 

나같은 경우에는 테케만 보고 맨끝이 제일 긴 비디오라 생각하여서 시작을 배열의 끝인 400부터 start로 잡고 갔는데,

이러한 반례가 존재한다.

따라서 리스트의 최대값을 찾고, 그것을 start로 해주고, end는 리스트의 총합을 넣어준다.

또한,

블루레이의 최솟값을 찾기위해 값을 비교할 때, 리스트의 최대값보다 작다면 결과값에 넣지 않도록 조건을 넣어주는 것이 중요하다.

if(mid >= max(video)):

            res = min(res, mid)

바로 이부분 !!!

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
video = list(map(int, input().split()))

vm = max(video)
start = vm
end = sum(video)

res = 10**9
while(start <= end):
    mid = (start+end)//2
    cnt = 1
    tmp = 0
    for i in range(n):
        if(tmp+video[i] <= mid):
            # 만약 현재 블루레이에 비디오를 더 넣을 수 있다면
            tmp += video[i]
        else:
            cnt += 1
            tmp = video[i]
        if(cnt > m):
            break
    if(cnt > m):
        start = mid+1
    else:
        end = mid-1
        if(mid >= vm):
            res = min(res, mid)

print(res)