백준 6236: 용돈 관리 - 이분 탐색(파이썬)

용돈 관리 성공다국어

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

 

내 코드

import sys
n,m=map(int, sys.stdin.readline().split())

money=[]
for _ in range(n):
    money.append(int(sys.stdin.readline()))

start=max(money) #n일동안 써야 하므로 적어도 돈의 최대값은 되야한다.
end=sum(money) #한번에 뽑아서 다 쓰는 경우가 가장 최대일 때.

answer=0
while start<=end:
    mid=(start+end)//2

    total=0
    cnt=0
    for x in money:
        if total+x<=mid:
            total+=x
        else:
            cnt+=1
            total=0
            total+=x
    if total: #마지막 돈에 대해서 total에 금액이 있으면 cnt++ 처리.
        cnt+=1

    if cnt>m: #횟수가 많으면 인출 금액을 늘려야 됨.
        start=mid+1
    else: #횟수가 적거나 같으면 인출 금액을 줄여야 됨.
        end=mid-1
        answer=mid

print(answer)

 

풀이 및 접근)

- 이분 탐색을 이용한 문제이다. 이런 이분 탐색은 start와 end의 초기값 세팅이 정말 중요하다. 이를 잘못 세팅하면, 계속해서 오답이 난다. 문제를 정확히 읽어보고 start와 end 값을 정확히 세팅해야한다. 그렇지 않으면 올바르지 않은 방향으로 이분 탐색이 진행된다.

- 그리고 문제에서 특정 값의 최대값을 원하는지, 최소값을 원하는지 파악한 후, answer을 어느 if문에 할당할지 잘 결정 해야한다.