[백준] 6236 용돈 관리
문제 설명
정확히 M번의 인출로 일일 소비량을 해결하려면 최소 금액 K를 어떻게 설정해야 하는지 물어보는 문제이다.
문제 풀이
이분 탐색은 어렵다. 그 개념, 혹은 구현하는 방법이 어렵다기 보다는 어떤 경우에 사용해야 하는지 아직도 감이 오지 않는다. 힌트를 보고서야 이분 탐색인 것을 파악을 했는데, 관련 문제를 많이 풀어보고 익숙해져야만 잘 풀 수 있을 것 같다.
접근하는 방법에 관련한 해설을 찾아보다가 꽤나 도움이 되는 걸 찾았다: 호우동의 개발일지 해당 블로그에서 말하길,
- 문제 조건에 부합하는 금액 K를 찾는 것이기 때문에 K의 범위를 점점 줄여나가며 찾는 탐색
- K는 무조건 가장 큰 일일 소비값보다 같거나 커야 하며, 모든 날의 소비 값의 합보다는 작아야 한다
특히 2번 조건 때문에 이진 탐색을 시작할 범위를 제한할 수 있으며, 이는 시간 복잡도 면에서 꽤 유리하여 이진 탐색을 선택했다고 한다. 이 두 가지를 생각하지 않은 것은 아니었으나, 나는 이를 직접적으로 이진 탐색으로 연결짓지를 못했다.
일단 이진 탐색인 것을 검색의 도움으로 확인했으니, 이를 코드로 옮겨보겠다.
우선 이진 탐색할 범위의 작은 끝을 left, 큰 끝을 right라고 설정해두고, 이 범위가 K값이 있는 범위라고 생각을 하면 left는 앞서 말한 ‘가장 큰 일일 소비값’이어야 하며, right값은 ‘모든 날의 소비 값의 합’이어야 할 것이다.
1
2
left = max(list)
right = sum(list)
이진 탐색의 특성 상 가운데를 기준으로 범위를 좁혀나가는 것이기 때문에 mid = (left + right)//2
로 설정하여 진행한다.
현재 인출한 돈을 cur
로 정의하여 일일 소비 배열의 수들을 문제의 조건에 따라 소비한다.
- 남은 인출된 돈보다 소비액이 적으면 인출된 돈에서 해당 액수 차감 후 다음 날 그대로 진행
- 남은 인출된 돈보다 소비액이 크면 다시
mid
값 인출 후 이를cur
로 설정, 재시도
이렇게 반복하여 나온 인출의 횟수 count
가 M보다 크면 탐색 범위의 left
를 mid+1
으로 변경하여 다시 탐색한다. 반대의 경우는 right
를 mid-1
으로 설정하여 다시 탐색한다. 다만, right가 변경되었을 경우에는 K
를 현재 나온 mid
값으로 정의해주어야 한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)