BOJ 2343 기타 레슨

https://www.acmicpc.net/problem/2343
시간 2초, 메모리 128MB
input :

• N M(1 ≤ N ≤ 100,000)(1 ≤ M ≤ N)
• 기타 레슨의 길이가 레슨 순서대로 분 단위로(자연수)

output :

• 가능한 블루레이 크기중 최소를 출력

---

어떤 것을 이분탐색 해야 하는가? 에 대한 것이 떠오르질 않았다.

가능한 블루레이의 최대 길이, 최소한의 길이 범위 사이에서 값을 찾아내야 한다.

mid 로 찾아낸 값에 레슨을 넣으면서 블루레이가 몇 개 만들어지는지 확인.

import sys

n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

lo = max(data)
hi = sum(data)
while lo <= hi:
    mid = (lo + hi) // 2
    cnt = 0
    full = 0
    for item in data:
        if full + item > mid:
            cnt += 1
            full = 0
        full += item
    if full > 0:
        cnt += 1

    if cnt > m:
        lo = mid + 1
    else:
        hi = mid - 1

print(lo)

while 조건에는 <=이 걸려야 한다.
hi = mid - 1 로 만들기 때문에 우리는 정답보다 -1 된 값을 계속 가지고 있는데 계산이 이루어지다 보면 마지막에 lo = mid + 1의 연산으로 lo가 정답을 가지도록 할 수 있는 것이다.

정렬을 할 수 없는 문제이기 때문에 맨 처음 lo를 초기화 할 때 max(data)를 이용한다.