[Python/파이썬] 백준 6236번 용돈 관리

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

 

코드

n, m = map(int, input().split())
money = [int(input()) for _ in range(n)]


def chk(k):  # m번 이하로 인출할 수 있는지
    if k < max(money):  # n일 중 가장 많이 쓰는 날보다 작아서는 안됨
        return int(1e9)
    tmp = 0
    cnt = 0
    for i in range(n):
        if tmp < money[i]:    # 인출
            tmp = k
            cnt += 1
        tmp -= money[i]  # i번째 날 사용
    return cnt


# 매개 변수 탐색
s, e = 0, int(1e9)
while s <= e:
    k = (s+e)//2
    if chk(k) <= m:
        e = k-1
    else:
        s = k+1

print(e+1)

 

매개 변수 탐색(Parametric Search)

조건을 만족하는지 안하는지 여부로 범위를 좁혀나가는 알고리즘이다. 이 문제에서의 조건은 한 번에 인출하는 금액은 k로 제한하고 n일 동안 m번만 인출하여 생활이 가능한지 여부이다. 이 때 정확히 m번을 맞추기 위해 필요 없을 때도 인출할 수 있으므로 m번 이하로 인출 가능한지 여부만 판단하면 된다.