9주차_#6236 용돈 관리

문제 이해 💬

적정하되, 최소인 인출 금액 K 찾기

• N : 금액을 계산할 일 수
• M : 통장에서 돈을 뺄 수 있는 횟수
• K : 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다

다만 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다.

적정하되, 최소인 인출금액 K를 찾자!

입력
1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)
2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

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

처음 든 생각 🤔

아놔 굉장히 큰 search 범위와, 적정하되 최소이다/최대이다 Parametic Search!

아놔 외우것다 외우것어 😀

수식

처음 짠 코드

#title 기본 제목 텍스트
n, m = map(int, input().split())
budgets = list(int(input()) for _ in range(n))


# 이진탐색
start = 0
end = sum(budgets)

while (start <= end) :
  mid = (start + end) // 2
  cur_budget= mid
  num = 1

  # 적정 기준 검사
  for i in range (n) :
    if cur_budget < budgets[i] : # 가진 돈이 부족할때
      cur_budget = mid
      num += 1
    cur_budget -= budgets[i]

  # m번보다 더 많이 인출하거나 인출한 금액이 하루에 부족한 경우 = 인출금액이 적음 = 오른쪽 탐색
  if num > m or mid < max(budgets) :
    start  = mid + 1
  else :
    end = mid - 1
    res = mid

print(res)

결과 ) 런타임 에러

다음 한 생각 💬

런타임 에러니까 검색해보니까 이진검색의 범위를 아예 처음부터 좁힐 수 있었다.
그래서 START를 리스트의 최솟값으로, END를 리스트의 최댓값으로 바꿔보았다.

# 이진탐색
start = 0
end = sum(budgets)

⬇️

# 이진탐색
start = min(budgets)
end = max(budgets)

결과) 런타임에러

ㅆ...