[백준 6236] 용돈 관리

문제설명

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

6236번: 용돈 관리

알고리즘

1. 사용할 수 있는 돈의 최소는 i일 동안 사용할 금액 중에 가장 큰 값, 그리고 돈의 최대는 모든 사용할 돈의 합이다

2. 해당 두 값으로 이분탐색을 진행한다

3. 이분탐색을 할 때, 돈 인출 수를 세어보고 더 많이 인출해야하는 경우 돈을 키우고 그렇지 않은 경우 금액을 줄인다

코드

import sys
 
def Input_Data():
    readl = sys.stdin.readline
    N, M = map(int,readl().split())
    need = [int(readl()) for _ in range(N)]
    return N, M, need
 
def Binary_Search():
    start = max(need)
    end = sum(need)
    while end >= start:  
        mid = (start + end) // 2
        if Check(mid): 
            end = mid -1
        else: 
            start = mid +1
    return mid 
 
def Check(val):
    cur = val
    cnt = 1
    for v in need:
        if cur < v: #돈을 인출해야하는 경우 
            cnt +=1
            cur = val 
        cur -= v #돈 사용
        if cnt > M: #더 많이 인출해서 돈 사용 -> 금액 늘릴 필요
            return False
    #더 적게 인출해서 돈을 사용할 수 있음 -> 금액 줄일 필요
    if cnt <= M:
        return True
 
sol = -1
N, M, need = Input_Data()
sol = Binary_Search()
print(sol)

고찰

이분탐색을 통해 쉽게 구현할 수 있는 문제였다