[백준 6236] 용돈 관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 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를 출력한다.

---

접근

문제를 분석했을 때 이진탐색으로 금액 K를 탐색하고 K를 인출할 때 M번 인출하게 되는지 검사를 하여 이진탐색의 범위를 좁혀나간다.

 

구현

- left는 입력받은 금액의 최댓값으로 설정하고 right는 N개의 금액 총합으로 설정한다.

- 이어서 이진탐색으로 진행하고 mid로 M번이 가능한지 여부를 따진다.

- 만약 M번 이하라면 right를 mid로, 반대의 경우에는 left를 mid+1로 하여 범위를 갱신한다.

- 여기서 이진탐색이 실행되는 조건이 left < right이기 때문에 right를 mid로 설정해야 최종해도 탐색할 수 있다.

left = max(numbers)
right = sum(numbers)

while left < right:
    mid = (left + right) // 2
    if is_possible(mid):
        right = mid
    else:
        left = mid + 1

- N개의 금액을 순차적으로 탐색하여 더해나가다가

- 전달받은 mid값인 target을 초과할 때 인출 횟수인 count를 증가시킨다.

- 인출횟수인 count가 M이하인지를 반환한다.

def is_possible(target):
    count = 1
    total = 0
    for number in numbers:
        total += number
        if total > target:
            total = number
            count += 1

    return count <= M

---

전체 코드

import sys
input = sys.stdin.readline

def is_possible(target):
    count = 1
    total = 0
    for number in numbers:
        total += number
        if total > target:
            total = number
            count += 1

    return count <= M
N, M = map(int, input().split())
numbers = [int(input()) for _ in range(N)]

left = max(numbers)
right = sum(numbers)

while left < right:
    mid = (left + right) // 2
    if is_possible(mid):
        right = mid
    else:
        left = mid + 1
print(right)