[이분탐색] 백준 6236. 용돈관리

문제 바로가기

문제 해석

하루 사용하는 금액과, 돈을 인출할 수 있는 횟수가 주어짐.
인출 횟수를 꼭 맞추고 하루 돈 소비량을 충족시킬 수 있는 최소 인출금액(mid로 탐색)을 구해라.
단, 인출 금액은 고정되고 돈이 부족하면(오늘 쓸 돈이 더 많으면) 입금했다가 재인출

주요 변수

기간 : n
인출 횟수 : m
매일 쓰는 금액 : cost list

탐색범위

   low : 매일 쓰는 금액의 최대값으로 맞춰준다, 문제 조건 N<M 에 따라 하루에 한 번 인출할 금액이 되어야 하기 때문에..

알고리즘 진행

답이 될 mid를 찾아나간다. mid는 인출 횟수를 기준으로 탐색 범위를 좁혀나간다.
인출 횟수가 주어진 조건 m 을 초과하면 안된다는 것이 조건이므로, m보다 작은 쪽에서 answer를 할당한다.

import sys
sys.stdin = open('.//이분탐색//input.txt', 'rt')
n, m = map(int, input().split())
print(n,m)
cost = [int(input()) for _ in range(n)]

# n 일 동안 쓸 돈
# m 번 인출
# k 원 인출

# 7일 동안 5번 인출 // 500원씩
ans = 500
low = max(cost)
high = 10**9


def getCnt(mid):
    res = mid # 500
    cnt = 1
    for i in range(n):
        if (res - cost[i]) < 0 :
            res = mid
            cnt+=1
        res -= cost[i]
    return cnt

while low <= high:
    mid = (low+high) //2
    if getCnt(mid) > m:
        low = mid + 1
    else:
        ans = mid
        high = mid -1

print(ans)

참고
https://ddb8036631.github.io/boj/6236_%EC%9A%A9%EB%8F%88-%EA%B4%80%EB%A6%AC/