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

6236번: 용돈 관리

풀이는 해당 블로그를 참고했습니다.

 

전형적인 이분 탐색 문제입니다만...

고려하지 못한 부분과 실수한 부분이 많아 이를 되짚어 보려합니다.

 

문제 풀이는 적절한 금액(조건을 만족하면서 최소가 되는)을 이분탐색으로 찾는 것입니다.

 

처음에 제가 잘못 생각한 것은 하루 소비 금액 > 뽑을 수 있는 금액(설정 금액) 이어도 하루에 여러번 돈을 뽑으면 된다는 것이었습니다.

문제에서 돈을 뽑을 때는 가지고 있는 돈을 모두 반환하고 뽑기 때문에 잘못된 생각입니다.

이 때문에 설정 금액을 초과하는 하루 소비 금액이 하루라도 있으면 설정 금액을 늘려줘야 합니다.

 

이 부분을 잘못 생각한게 컸습니다. 이걸 잘못 하니까 생각이 계속 꼬이더군요...

 

파이썬 코드

import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
days = []
for _ in range(N):
    days.append(int(readline()))

answer, left, right = sum(days), 0, sum(days)

while left <= right:
    mid = (left + right) // 2
    count, money = 0, 0
    lack = False

    for d in days:
        if mid - d < 0:
            # 돈을 뽑아도 하루를 못 넘기면
            lack = True
            break
        elif money - d < 0:
            money = mid
            count += 1
        money -= d

    # 돈이 부족한 날이 없으면
    if not lack:
        # 목표 횟수보다 count가 같거나 작으면 돈을 줄임
        if count <= M:
            right = mid - 1
            if mid < answer:
                answer = mid
        # 목표 횟수보다 count가 크면 돈을 늘림
        elif count > M:
            left = mid + 1
    # 돈이 부족한 날이 있으면 무조건 돈을 늘림
    else:
        left = mid+1

print(answer)