[코딩테스트] 용돈 관리

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

문제 분석

우선 시간 제한은 1초이고, 메모리 제한은 128MB, N의 경우에는 100000까지 제한이 되어있습니다.

당연하게도 $O(N^2)$은 허용이 되지않고, $O(NlogN)$의 복잡도까지만 허용이 되어있습니다. 그러므로 이 문제는 이분탐색으로 접근을 하는게 합리적일 것으로 보입니다.

이제 풀이 전략을 세워보겠습니다.

풀이를 어떻게 해야할까요?

저희가 구해야하는 것은, 현우가 매번 인출해야하는 금액의 최솟값을 이분탐색을 통해서 구해야합니다.

그런데, 현우가 매번 인출해야하는 금액에는 조건이 하나 붙습니다. 현우가 사용하는 금액의 최댓값보다는 크거나 같아야합니다. 이유는, 인출해야하는 금액이 사용할 금액보다 작은 경우에는 인출하고도 비용 사용을 못 하기 때문입니다.

따라서, 위의 조건을 이분탐색 과정에서 포함해야될 필요가 있습니다.

코드를 확인하면서 설명을 해드리겠습니다.

import sys

input = sys.stdin.readline

# 6236 용돈관리
N, M = map(int, input().split())
money_list = []

for _ in range(N):
    tmp = int(input())
    money_list.append(tmp)
    
balance = 0
start, end = min(money_list), sum(money_list)
mid = 0

while start <= end:
    mid = (start + end) // 2
    count = 1
    balance = mid
    
    for money in money_list:
        if balance < money:
            balance = mid
            count += 1
        balance -= money
            
    if count > M or mid < max(money_list):
        start = mid + 1
    else:
        end = mid - 1
        
print(start)

일단 최초에 while문을 들어갈 때, 돈을 일단 한 번 뽑고 시작합니다. 돈을 뽑았기 때문에 balance에는 mid만큼의 돈이 남고, count는 1이 됩니다.

그리고 for문에 진입해서 사용할 금액의 리스트를 선형으로 탐색합니다. 만일 balance가 모자란 경우에는 balance를 채우고 count를 1 증가시킵니다.

만일 돈이 충분하다면 balance에서 money만큼 금액을 차감하면 되겠죠?

그리고 마지막에는 count > M인 경우에는 인출 금액이 작다는 뜻 이기 때문에, start를 키워서 인출 금액을 키웁니다. 그리고 mid가 충분하지 않은 경우도 마찬가지, start를 키웁니다.

반대의 경우에는 end를 줄여서 인출 금액의 크기를 줄여버립니다.

그렇게 해서 start를 출력시키면 문제는 해결됩니다.

위의 해결 방법에서 start를 min(money_list) 로 두었는데, max(money_list) 로 두는것이 제가 설명한 풀이에 제일 합당한 방법일겁니다.
그래도 min으로 둔 것과는 복잡도의 큰 차이는 보이지 않으니 성공은 했지만, max로 두면 더 최적의 풀이가 될겁니다!