2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
아이디어:
블루레이 크기를 이분 탐색. high = 10^9, low = 1
레슨의 길이를 더하다가 mid보다 같거나 커지면 블루레이 개수 +1
레슨의 길이가 M보다 크면 low = mid + 1, 같거나 작으면 블루레이 크기를 더 줄여야 하니까 high = mid - 1하고 ans 업데이트
import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
high = 10**9
low = 1
ans = high
while (high>=low):
mid = (high+low)//2
num = 0
time = 0
for i in arr:
if (i>mid): #블루투스의 크기가 레슨의 길이보다 작은 경우
num = m+1 #low = mid + 1이 되도록
break
time+=i #레슨의 길이 더하기
if (time>mid): #mid보다 커지면 자르기
num+=1
time = i
elif (time==mid):
num+=1
time = 0
if (time<mid and time!=0):
num+=1 #마지막에 남는 부분
if (num>m):
low = mid + 1
elif (num<=m):
high = mid - 1
ans = min(ans, mid) #자른 부분의 개수가 m보다 작으면 답 업데이트
print(ans)
※ ans = min(ans, mid) -> 이분탐색이라 그런건지 숫자가 왔다갔다 해서 최솟값으로 갱신해야 하더라
※ num==m일때만 값을 갱신하니 틀렸다. num<m 이면 더 잘게 쪼갤 수 있다는 말이니까 포함해야 한다. 그런 경우도 가능하더라고..
7 7
5 9 6 8 7 7 5
답: 9
--> 이런 경우..
'알고리즘💻 > 이분탐색&정렬&분할정복' 카테고리의 다른 글
BOJ 1026번: 보물 (0) | 2021.01.29 |
---|---|
BOJ 2470번: 두 용액 (0) | 2021.01.25 |
BOJ 16401번: 과자 나눠주기 (0) | 2021.01.25 |
BOJ 3079번: 입국심사 (0) | 2021.01.25 |
BOJ 1920번: 수 찾기 (0) | 2021.01.25 |