백준 6236번 용돈관리(파이썬)

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)
2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

풀이

전형적인 이분탐색 문제이다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
day_money = list(int(input())for _ in range(n))
start_money = min(day_money)
total_money = sum(day_money)

while start_money <= total_money:
    mid = (start_money + total_money) // 2
    #얼마를 뽑아야 할지 일단 중간값으로 확인한다.
    now_money = mid
    #현재 뽑은값이 현재 가지고 있는 돈
    cnt = 1
    #돈을 1번 뽑았으니 cnt도 1로 설정해두기
    
    for i in range(n): 
    #N일동안 매일 사용할 금액을 출력하는 과정
        if now_money < day_money[i]: 
        #현재 가지고 있는 돈이 그 당일에 쓸 돈보다 모자르면
            now_money = mid 
            #mid원을 인출한다
            cnt += 1 
            #인출했으니 인출횟수 1추가
        now_money = now_money - day_money[i] 
        #반복문을 돌면서 인출한 돈에서 하루마다 쓸 돈을 빼준다.
        
    if cnt > m or mid < max(day_money):
    #만약 인출횟수가 사용자가 지정한 m번보다 많거나
    #가장 많이쓰는날의 돈보다 인출한 돈이 적다면 돈이 부족하다는 말이므로
        start_money = mid + 1 
        #초기에 가지고 있는 돈을 인출한 돈에 + 1을 해준다.
        #이렇게 되면 이제 (mid+1)원을 인출할 수 있다
    else: 					  
    #돈이 충분했었다면
        total_money = mid - 1 
        #mid원까지 인출 할 필요가 없다. 앞으로 (mid-1)원을 인출한다.
        
print(start_money) #필요한 최소금액 k를 구하는 문제이므로
                   #while문이 끝난 초기에 가지고 있는 돈이 최소 금액이다.