[백준/파이썬]6236 용돈 관리

https://www.acmicpc.net/problem/6236

6236번: 용돈 관리

 

문제

 

백준 6236번 용돈 관리

 

이분 탐색 알고리즘 문제 풀어보는 중인데, 너무 헷갈리는 게 많은 알고리즘이다.

 

문제를 풀때 한번 만에 풀리는 경우가 거의 없는 것 같다. 조금씩 고치면서 때려 맞추는 느낌.. 깔끔하게 풀고 싶다.

 

 

 

문제는 각 일차에 필요한 금액이 주어지고, 인출 가능 횟수가 주어진다.

 

시중에 있는 돈이 각 일차에 필요한 금액보다 적을 경우에 다시 인출 가능하다. (여기서 시중에 있던 금액 + 인출 금액이 아닌, 인출 금액 k만큼만 인출됨)

 

인출할 금액은 k로 이 k값이 가장 적어 짐과 동시에 인출 횟수를 맞출 수 있는 k값을 찾는 문제다.

 

시작 : 1

끝 : sum(각 일차에 필요한 금액)

이렇게 범위를 지정했다. (이 범위 지정하는 것도 어려운 것 같다.)

 

끝 범위를 20000으로 했다가 틀렸다. 왜 틀리는지 아직 잘 모르겠다..

 

 

정답

import sys

input = sys.stdin.readline

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

lt = 1
rt = sum(arr)
k = 10000
while lt <= rt :
    mid = (lt+rt) // 2
    money = mid
    cnt = 1

    for num in arr :
        if money < num :
            cnt += 1
            money = mid
        money -= num
    
    if cnt > m or mid < max(arr):
        lt = mid + 1
    else :
        rt = mid - 1
        k = mid


print(k)