[6236] 용돈관리 in python

 

이분탐색으로 풀어야하는 문제

인출금액(k)와 인출횟수(cnt)의 값은 반비례한다는 것에 주목해야 한다.

 

통장에서 인출하는 금액의 값이 이용금액보다 모자라게 되면

남은 금액은 통장에 집어넣고 다시 k원을 인출한다.

그러면 인출하는 횟수는 늘어나게 된다.

 

따라서 인출하는 금액의 값이 인하되어야

인출하는 횟수를 늘릴 수 있기 때문에

반비례 관계라고 말할 수 있다.

 

계산한 cnt (인출횟수)의 값이 m값보다 작으면 -> 

k의 값을 감소시켜야하므로

right=mid-1

 

cnt의 값이 m값보다 크거나 같으면 ->

k의 값을 증가시켜야하므로

left=mid+1

 

 

# 1/12일
n, m = map(int, input().split())
array = [int(input()) for _ in range(n)]

left = min(array)
right = sum(array)
answer = sum(array)  # 최댓값

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    money = 0
    button = False

    for now in array:
        if mid - now < 0:
            # 출금하더라도 이용할 금액에 미치지 못하는 경우
            # K원 < 이용금액
            button = True
            break
        if money - now < 0:
            money = mid
            cnt += 1
        money -= now

    if not button:
        if cnt > m:
            left = mid + 1
        else:
            right = mid - 1
            answer = min(mid, answer)
    else:
        # K원<이용 금액이므로 k원의 값을 올려줘야한다.
        # 따라서 left=mid+1로 변경해줌으로써 mid(k)의 값을 올려준다.
        left = mid + 1
print(answer)
'''
N일 동안, M번만 돈을 뺸다. (M번만 빼야한다)
k>=이용금액 -> 0
현재 가지고 있는 돈 < 오늘 써야하는 금액 -> 현재 가지고 있는 돈을 통장에 넣고, k원을 출금 

'''

---