[python] 백준 2343 기타 레슨

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

2343번: 기타 레슨

 

문제 해결

블루레이 크기란 무엇인가? => 컴퓨터 메모리로 생각하면 편하다. ex) 블루레이 크기 17이면 수의 합이 17이 될 때 까지만 메모리 저장 가능

메모리 크기는 강의 길이가 가장 큰거 이상이여야 한다.

메모리 크기는 모든 강의 길의 합 이하여야 한다.

따라서 메모리 크기의 최소지점과 최대지점 투 포인터를 집아 이분 탐색을 해서 블루레이 크기중 최소를 출력하도록 한다.

 

CODE

import sys
input = sys.stdin.readline

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

start = 0
for i in A:
	if start < A[i]:
    	start  = A[i]
	end += A[i]

while start <= end:
	mid = int((start+end)/2)
    sum = 0
    count = 0
    for i in range(n):
    	if sum + A[i] > mid:
        	count += 1
            sum = 0
        sum += A[i]
    if sum != 0:
    	count += 1
    if count >m:
    	start = mid + 1
    else:
    	end = mid - 1
print(start)