[알고리즘] 백준 6236 - 용돈 관리

문제

용돈 관리

접근

1. 돈을 쓰고 남았다면, 다시 통장에 넣었다가 인출이 가능하다는 점을 사용하자

2. start와 end를 배열의 최소와, 배열의 합으로 설정을 하자

3. 오늘 사용할 금액을 배열로 부터 뽑아와서 잔고와 비교해서 잔고가 더 작다면 count를 증가시켜준다

4. 오늘 사용할 금액이 잔고보다 적다면 (잔고 - 오늘 사용할 금액)

5. Count가 총 횟수보다 많거나 mid값이 array의 최댓값보다 작으면 start를 이동

6. 아니라면 end를 이동하고, res에 end를 넣어준다

 

풀이

# 6236 용돈 관리
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

start = min(array)
end = sum(array)
res = 0

while start <= end:
    mid = (start + end) // 2
    balance = 0  # 잔고
    count = 0  # 인출횟수

    for today in array:  # 오늘 사용할 금액 체크
        if balance < today:
            balance = mid
            count += 1

        balance -= today  # 잔고에서 오늘 사용할 금액 빼기

    # 인출횟수가 m보다 많거나 mid가 최대 예산보다 작으면 mid값 증가시키기
    if count > m or mid < max(array):
        start = mid + 1
    else:
        end = mid - 1
        res = mid

print(res)