baekjoon 6236: 용돈 관리

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

6236번: 용돈 관리

---

이진탐색문제.

반례에 대해서 생각을 해보니, 하루지출 금액보다 인출하는 돈이 더 적으면 하루를 넘어 갈 수 없다.

 

이부분만 잘 생각한다면 다른 기본 이진탐색과 큰 차이가 없음

n,m = list(map(int,input().split()))
arr = [0]*n
for i in range(n):
    arr[i] = int(input())

st = min(arr)
ed = sum(arr)

while st <= ed:
    mid = (st + ed)//2

    k = 0 # 지불해야 하는 금액
    cnt = 1
    for i in range(n):
        if mid - (k+arr[i]) >=0:
            k += arr[i]
            continue
        else:
            cnt+=1
            k = arr[i]
    # m번보다 더 많이 인출하거나 인출금액이 하루의 사용금액보다 더 적은경우
    if cnt > m or mid < max(arr):
        st = mid +1
    else:
        ed = mid -1
        l = mid

print(l)