[백준] 6236. 용돈 관리

문제

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

6236번: 용돈 관리

 

설계

- 이분탐색

- 처음 주머니에 금액을 충전하고 카운트 + 1

- 모자라면 남은 금액을 통장에 집어넣고 K원 인출하는 조건

- answer는 K 가 end에서만 최신화

N, M = map(int, input().split())
arr = [int(input()) for _ in range(N)]

start, end = 1, sum(arr)        # end : 한번의 충전으로 모두 사용할 수 있는 최대금액 설정
while start <= end:
    K = (start + end) // 2
    pocket = K      # 주머니 충전
    cnt = 1     # 처음 충전 카운트

    for i in range(N):
        if pocket - arr[i] < 0:   # 다음날 사용할 돈이 없으면 충전
            pocket = K        # 모자라면 남은 금액은 통장에 집어넣고 K원 인출
            cnt += 1
        pocket -= arr[i]

    if M < cnt or K < max(arr):    # 충전금액이 최소한 하루에 사용할 금액보다는 커야한다.
        start = K + 1
    else:
        end = K - 1
        answer = K

print(answer)