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	예제 출력1
7 5 100 400 300 100 500 101 400	500

---

import sys
n, m = map(int, input().split())
days = [int(sys.stdin.readline()) for _ in range(n)]

low, high = max(days), sum(days)
k = sum(days)

while (low <= high):
	mid = (low + high) // 2
	m_cnt = 1
	k_temp = mid
	for i in days:
		if (i <= k_temp):
			k_temp -= i
		else:
			m_cnt += 1
			k_temp = mid
			k_temp -= i

	if m_cnt > m:
		low = mid + 1
	else:
		high = mid - 1
		if k > mid:
			k = mid

print(k)

---

N일 동안 각 날짜별 사용할 금액을 입력받고, K원을 최대 M번 출금하도록 하는 K의 최소값을 구하는 문제이다.

문제에서 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.가 나타내는 의미는 K의 최소값으로 N일 동안 사용할 금액을 출금할 때 출금 횟수가 M을 꼭 채우지 않아도 된다는 뜻이다.

문제에서 사용한 알고리즘은 이분탐색이다. 출금할 값 K의 범위를 low~high로 정해놓고 해당 범위를 이분탐색하며 K의 최소값을 구했다.

low값은 K가 가질 수 있는 최소값인 max(days)로 셋팅해주고, high값은 전체 금액을 더한 값인 sum(days)로 셋팅해 주었다.
만약 low값이 N일 중 최대 사용 금액보다 작다면 해당 날짜에는 아무리 출금을 해도 사용 금액을 채울 수 없기 때문에 0이 아닌 max(days)로 설정했다. high값은 K의 최소값을 구하는 것이기 때문에 아무리 커도 sum(days)를 넘기지 않는다.

mid값을 임시k값인 k_temp에 대입한 후 while문 안의 첫번째 for문을 통해서 설정한 k_temp로 출금 횟수(m_cnt)를 구한다. 이후 m_cnt와 입력받은 m의 값을 비교하여 범위를 조정하고, low값이 high의 값을 넘기기 전까지 재설정한 mid값으로 m_cnt를 구한다.

최종적으로 출력 할 k값은 m_cnt가 m보다 작거나 같을 경우에 mid와 기존의 k값 중 더 작은 값을 넣어준다.