[Python] 6236번 용돈 관리

✏️ 문제

문제 파악

이거 푼다고 시간 진짜 많이 잡아먹었다.... start를 최대값이 아닌 최소값으로 주고 하니 값이 자꾸 안나왔다 ㅠ

 

알고리즘

• 매개 변수 탐색
• 이분 탐색

 

 

코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
amount = [int(input()) for i in range(n)]

start, end = max(amount), sum(amount)
while start <= end:
  mid = (start+end) // 2
  cnt = 1
  changes = mid

  for i in amount: 
    if changes - i < 0:
      cnt += 1
      changes = mid
    changes -= i 

  if cnt <= m:
    end = mid - 1
  else:
    start = mid + 1

print(mid)