6236번 용돈 관리

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

---

아이디어

문제 설명이 진짜 난해하다...

현우는 N일 동안 사용할 금액이 입력으로 주어지고 통장에서 M번, K원을 빼서 사용한다.

예제 1번에서
100 400 300 100 500 101 400이 입력으로 주어졌다.
M = 5, K = 500이라고 하면

처음에 500을 인출하여 1,2 day 딱 맞춰서 쓴다.
3day 때 500을 인출하여 300 쓰고 200이 남으므로 4day 100도 쓴다.
그럼 100이 남는데 5day 때 써야하는건 500이므로 부족하다. 100은 통장에 넣고 또 500을 인출하여 쓴다. 남은건 0이므로 6day 때 500 인출하여 101 쓰고 399 남는데 7day는 400이므로 500을 또 인출해야한다.
그럼 인출한 횟수는 M으로 딱 맞는다.

이 K를 이진탐색으로 찾으면 된다.
low = max(주어진 리스트)
high = sum(주어진 리스트)로 잡았다.

---

코드

import sys
input = sys.stdin.readline

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

low = max(money)
high = sum(money)
answer = 0

while low <= high:
    mid = (low+high)//2
    cnt = 1
    temp_mid = mid
    for i in range(n):
        if temp_mid >= money[i]:
            temp_mid -= money[i]
        else:
            temp_mid = mid - money[i]
            cnt += 1

    if cnt <= m:
        high = mid - 1
        answer = mid
    elif cnt > m:
        low = mid + 1
print(answer)