[백준/python] 6236번 용돈관리

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

6236번: 용돈 관리

 

문제분석

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

정리하면, N개의 수에서 합이 K이하인 M개의 그룹으로 묶을 때, K의 최솟값을 찾는 것이다.

 

코드

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
budget = [int(input()) for i in range(n)]
lo = min(budget)
hi = sum(budget)
ans = 0

while lo <= hi:
    mid = (lo + hi) // 2

    total = 0
    count = 0
    for today in budget:
        if total < today:
            total = mid
            count += 1
        total -= today

    if count > m or mid < max(budget):
        lo = mid + 1
    else:
        hi = mid - 1
        ans = mid

print(ans)

 

문제풀이

1. N과 M 그리고 N개의 금액들을 입력받는다.

2. K를 탐색하기 위해서 최소로 인출할 수 있는 금액을 min(budget)으로 설정하고, 가장 최대로 인출할 수 있는 금액을 sum(budget)으로 설정한다.

3. while문으로 이진 탐색을 시작한다. 범위를 2로 나눠서 mid에 목표값을 설정하고, 목표값에서 count로 몇 번 출금을 하는지 확인한다.

4. 인출 횟수가 m보다 많거나 mid가 예산의 최댓값보다 작으면 mid값 증가시켜 다시 탐색을 한다.

5. 인출 횟수가 m과 같거나 m보다 적으면 mid값 감소시켜 다시 탐색을 한다.

6. 탐색이 끝나면, 출력을 하고 종료한다.