9주차_#2343 기타 레슨

문제 이해 💬

블루레이 길이의 적정 최소 값을 구하시오

• 블루레이에는 총 N개의 강의가 '순서대로' 들어감

• 강의는 짤려서 못들어간다 (들어갈려면 통채로 탑재되어야)

• 모든 블루레이는 같은 크기 가짐

• 강의수 : N / 블루레이의 갯수 : M

입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다.
다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다.
각 강의의 길이는 10,000분을 넘지 않는다.

출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

처음 든 생각 🤔

조낸 큰 집단 중 조건에 맞는지 검색? 이진검색!
근데 적정값 찾기? Parametic Search!

수식

처음 짠 코드👩🏻‍💻

n, m = map(int, input().split())
lessons = list(map(int, input().split()))
start, end = max(lessons), sum(lessons)

# 이진탐색 시작
while start <= end:
	#적정조건 검사
	mid = (start + end) // 2
	cnt = 0
	length = 0
	for i in lessons:
		# length m보다 커지면 새로운 dvd 필요
		if length + i > mid:
			cnt += 1
			length = 0
		length += i
	cnt += 1 if length else 0

	if cnt <= m:
		end = mid - 1
	else:
		start = mid + 1

print(start)

오 통과~