[ 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를 출력한다.

---

풀이 과정

---

1. 인출할 금액 K의 최소 금액을 N일동안 사용할 금액 중 최댓값으로 하고, 최대 금액을 10000 * 100000으로 하여 이분탐색 진행
   • 이유는, 적어도 한번에 인출한 금액이 매일매일 사용하는 금액보다는 커야 하기 때문이다.
   • 또한, 최대 금액같은 경우는 매일매일 10000원씩 10만일(N) 사용하는데, 인출을 한번만 하는 경우에는 10000 * 100000원 인출하여야 하기 때문이다.
2. 이분탐색 진행 시 중간값으로 시뮬레이션 한다.
   • 중간값 기준으로 M번 이하 인출하는지 확인하고, 그렇다면 정답에 저장해두고 왼쪽 구간 진행
   • M번 이상 인출한다면, 오른쪽 구간 진행
3. 저장해둔 정답을 출력하면 된다.

---

소스 코드

---

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
moneys = [int(input().rstrip()) for _ in range(N)]
mx_moneys = max(moneys)

left = mx_moneys
right = 10000 * 100000

answer = 0
while left <= right:
    mid = (left + right) // 2
    days = 1
    p = mid
    for money in moneys:
        if p - money < 0:
            p = mid
            days += 1
        p = p - money

    if days <= M:
        answer = mid
        right = mid-1
    else:
        left = mid+1

print(answer)