[백준][Python] 6236 용돈 관리

실버 2 / 이분 탐색

🤑

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

 

내 풀이

N, M = map(int, input().split())
money = [int(input()) for _ in range(N)]
s, e = max(money), sum(money)
ans = 0

while s <= e:
    total = 0
    result = 0
    mid = (s + e) // 2

    for m in money:
        if result + m > mid:
            result = 0
            total += 1
        result += m

    if result > 0:
        total += 1

    if total > M:
        s = mid + 1
    else:
        e = mid - 1
        ans = mid

print(ans)

 

 

코드 설명

s, e = max(money), sum(money)

s: 인출할 금액의 시작점

e: 인출할 금액의 끝점

 

1 ≤ M ≤ N 조건이 있으므로, s는 현우가 이용할 최대 금액 이상이 되어야 한다.

모든 금액을 한 번에 인출하는 경우가 존재할 수 있으므로, e는 현우가 이용할 금액의 합으로 설정한다.

 

✔️ while문 내

total = 0
result = 0
mid = (s + e) // 2

total: 돈을 인출할 횟수

result: 사용한 금액의 합

mid: 인출할 금액

 

for m in money:
    if result + m > mid:
        result = 0
        total += 1
    result += m

result에 오늘 쓸 금액을 더하면서 mid(인출할 금액)보다 커지면 result(사용한 금액의 합)를 0으로 초기화하고 total(돈을 인출할 횟수)를 늘린다.

여기서 포인트는 돈이 모자라게 되면, 남은 금액을 통장에 집어넣고 다시 K원을 인출한다는 것이다.

즉, 돈이 모자라면 남은 돈은 버려지고 인출한 금액 K원만 재생성되는 것!

 

if result > 0:
    total += 1

result에 남은 값이 있다면 인출 횟수를 1 늘려준다.

 

if total > M:
    s = mid + 1
else:
    e = mid - 1
    ans = mid

1. total(돈을 인출할 횟수)가 M보다 큰 경우

인출 횟수를 줄여야하므로 인출 금액을 늘린다. (s = mid + 1)

 

2. total(돈을 인출할 횟수)가 M보다 작거나 같은 경우

더 최선의 결과가 있는지 확인하기 위해 인출 금액을 줄인다. (e = mid - 1)

문제의 조건을 충족한 것이기 때문에 ans에 현재 인출 금액인 mid를 넣는다.

 

⚡️

 

문제를 풀다가 의문이 드는 부분이 있었다.

정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다.

 

지문에 다음과 같은 내용이 있어서 total == M일 때만 ans = mid를 수행하도록 했었는데 이렇게 하니까 틀린다.

오역인가,,?🤔

 

결론은 M번 이하의 인출을 해줘야 함!