[백준] 6236 용돈 관리

문제 설명

문제 링크

정확히 M번의 인출로 일일 소비량을 해결하려면 최소 금액 K를 어떻게 설정해야 하는지 물어보는 문제이다.

문제 풀이

이분 탐색은 어렵다. 그 개념, 혹은 구현하는 방법이 어렵다기 보다는 어떤 경우에 사용해야 하는지 아직도 감이 오지 않는다. 힌트를 보고서야 이분 탐색인 것을 파악을 했는데, 관련 문제를 많이 풀어보고 익숙해져야만 잘 풀 수 있을 것 같다.

접근하는 방법에 관련한 해설을 찾아보다가 꽤나 도움이 되는 걸 찾았다: 호우동의 개발일지 해당 블로그에서 말하길,

1. 문제 조건에 부합하는 금액 K를 찾는 것이기 때문에 K의 범위를 점점 줄여나가며 찾는 탐색
2. K는 무조건 가장 큰 일일 소비값보다 같거나 커야 하며, 모든 날의 소비 값의 합보다는 작아야 한다

특히 2번 조건 때문에 이진 탐색을 시작할 범위를 제한할 수 있으며, 이는 시간 복잡도 면에서 꽤 유리하여 이진 탐색을 선택했다고 한다. 이 두 가지를 생각하지 않은 것은 아니었으나, 나는 이를 직접적으로 이진 탐색으로 연결짓지를 못했다.

일단 이진 탐색인 것을 검색의 도움으로 확인했으니, 이를 코드로 옮겨보겠다.

우선 이진 탐색할 범위의 작은 끝을 left, 큰 끝을 right라고 설정해두고, 이 범위가 K값이 있는 범위라고 생각을 하면 left는 앞서 말한 ‘가장 큰 일일 소비값’이어야 하며, right값은 ‘모든 날의 소비 값의 합’이어야 할 것이다.

left = max(list)
right = sum(list)

이진 탐색의 특성 상 가운데를 기준으로 범위를 좁혀나가는 것이기 때문에 mid = (left + right)//2로 설정하여 진행한다.
현재 인출한 돈을 cur로 정의하여 일일 소비 배열의 수들을 문제의 조건에 따라 소비한다.

• 남은 인출된 돈보다 소비액이 적으면 인출된 돈에서 해당 액수 차감 후 다음 날 그대로 진행
• 남은 인출된 돈보다 소비액이 크면 다시 mid값 인출 후 이를 cur로 설정, 재시도

이렇게 반복하여 나온 인출의 횟수 count가 M보다 크면 탐색 범위의 left를 mid+1으로 변경하여 다시 탐색한다. 반대의 경우는 right를 mid-1으로 설정하여 다시 탐색한다. 다만, right가 변경되었을 경우에는 K를 현재 나온 mid 값으로 정의해주어야 한다.

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
list = []
for _ in range(N):
    list.append(int(input().rstrip()))
left = max(list)
right = sum(list)

while left <= right:
    mid = (left + right) // 2
    cur = mid
    count = 1  
    for i in range(N):
        if cur < list[i]:
            cur = mid
            count += 1
        cur -= list[i]

    if count > M or mid < max(list):
        left = mid + 1
    else: 
        right = mid-1
        K = mid

print(K)