백준[ 6236 | Python ] 용돈 관리

문제

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

풀이

먼저 탐색해야 할 것은 인출해야할 금액 K이다. 따라서 어느 경우라도 인출할 수 있는 최소의 금액 l은 행렬의 최소값,
가장 최대로 인출하게 될 경우의 금액은 행렬을 모두 더한 값이 될 것이다.

이 탐색 범위 안에서 고려해야할 것은 인출횟수 M과 현재 가지고 있는 돈이다.

이분탐색을 하면서 당일 가지고 있는돈, 예산을 비교해가며 K값을 찾는다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
budget = [int(input()) for _ in range(N)]
l,r = min(budget), sum(budget)
while l <= r:
    m = (l+r)//2
    now = m
    draw = 1

    for i in budget:
        if now < i:
            now = m
            draw+=1
        now -= i
    
    if draw > M or m < max(budget):
        l = m+1
    else:
        r = m-1
        k = m
print(k)

생각 & 정리

문제 이해부터가 쉽지 않은 문제였다.
시작금액이 얼마인지 찾고 생각하다가 예제를 문제를 여러번 읽고는 이해했는데, 어떤 값을 대상으로 이분탐색을 해야할지 생각하지 못하고 다른 분의 코드를 참고하여 이해했다.

참고

https://velog.io/@deannn/BOJ-백준-6236-용돈관리-Python