백준 6236 용돈 관리(이분 탐색)

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

6236번: 용돈 관리

K원을 통장에서 빼서 K원을 가지고 일주일 동안 몇번을 뺄 수 있는지 검사하는 문제이다.

 

K의 범위는 max(money) ~ sum(money) 이다

=> 일단 sum(money)를 가지고 있으면 통장에서 돈 뺄일 없이 가지고 있는 돈으로 계속 활용 가능하기 때문

=> 사실상 K는 1부터 시작해도 되긴함. 하지만 max(money)값 부터 시작하는 이유는 1 ≤ M ≤ N 조건 때문인데

n이 7이라면 m의 최댓값은 7이 될텐데 7번 모두 무사히 빼려면 max(money)를 들고있어야 가능함

 

n,m = list(map(int,input().split()))
money = []
for _ in range(n):
    money.append(int(input()))

start = max(money)
end = sum(money)
res = 0
while start <= end:
    mid = (start+end)//2
    temp = mid
    cnt = 1
    for i in range(n):
        if temp < money[i]:
            temp = mid
            cnt += 1
        temp -= money[i]
    if cnt > m:
        start = mid + 1
    else:
        end = mid - 1
        res = mid
print(res)