[이분탐색] 백준 #6236 용돈 관리 - Python

🗂️ 문제

문제

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

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입력 1

7 5
100
400
300
100
500
101
400

예제 출력 1

500

 

💡 접근법

이분탐색의 경우 범위를 좁혀 나갈 기준을 제대로 설정하는 것이 중요하다.

해당 문제에서는 필요한 최소 금액을 구하는 것이므로, 금액을 기준으로 범위를 좁혀나가야 함을 알 수 있다.

 

기준을 지정했으면 low와 high를 설정해야 한다.

문제에서는 "금액이 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다"고 했다.

따라서 인출한 금액만으로 하루 소비액을 처리할 수 있어야 한다. 그러므로 low를 하루 소비액 중 최댓값으로 설정해야 한다.

 

low와 high를 좀 더 쉽게 설정하는 팁은 다음과 같다.

문제에서는 M번만 통장에서 돈을 인출한다고 했다. 따라서 이분탐색으로 비교해야 할 값은 M이다.

즉, M의 범위를 생각해본 뒤 범위의 최소값과 최댓값을 기준으로 low와 high를 생각해보자.

1. M의 범위는 1 ≤ M ≤ 7이다.
2. M=1이 의미하는 것은 통장에서 돈을 한 번만 인출한다는 것이다.
   돈을 한 번만 인출해서 모든 소비를 처리하기 위해서는 모든 소비액의 합(sum(spend_money))만큼의 금액이 필요하다.
3. M=7이 의미하는 것은 통장에서 돈을 7번 인출한다는 것이다.
   즉, 돈을 매일 인출한다는 것인데 매일 인출하기 위해서는 하루 소비액의 최댓값(max(spend_money))만큼의 금액이 필요하다.

 

😎 내 코드

import sys

N, M = map(int, sys.stdin.readline().split())
spend_money = [int(sys.stdin.readline()) for _ in range(N)]

low = max(spend_money)
high = sum(spend_money)

while low <= high:
    current_money = 0  # 현재 남은 금액
    withdraw_cnt = 0  # 돈을 인출한 횟수

    mid = (low + high) // 2

    for money in spend_money:
        if current_money - money < 0:  # 사용할 금액이 남은 금액보다 큰 경우 -> 돈 인출
            current_money = mid
            withdraw_cnt += 1
        current_money -= money
    
    if withdraw_cnt <= M:  # 돈 인출 횟수가 적은 경우 -> 인출 금액을 줄여야 함
        high = mid - 1
    elif withdraw_cnt > M:  # 돈 인출 횟수가 많은 경우 -> 인출 금액을 높여야 함
        low = mid + 1

print(low)

 

✅ 정답 확인