https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
n, m = map(int, input().split())
arr = list(map(int, input().split()))
result = sum(arr)
start = 0
end = sum(arr)
while start <= end:
mid = (start + end) // 2
cnt = 1
ray_len = 0
if mid < max(arr):
start = mid + 1
continue
for i in range(len(arr)):
if ray_len + arr[i] <= mid:
ray_len += arr[i]
else:
ray_len = arr[i]
cnt += 1
if cnt <= m:
end = mid - 1
result = min(result, mid)
else:
start = mid + 1
print(result)이분탐색이다.
우선 mid값을 어떻게 설정해야 할지 참 애매했다.
mid값은 블루레이의 길이로 지정하고 for문을 돌며 ray_len변수에 블루레이의 길이(합)을 담는다.
그리고 ray_len이 mid보다 크다면 cnt+1을 시켜주고 ray_len을 arr[i]로 초기화 시켜준다.
그 외엔 전부 구현 문제인 것 같았다.