[#6236] 용돈 관리

RookieAND·2022년 7월 6일

백준 이분탐색 코테

BaekJoon

목록 보기

25/42

❓ Question

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

📖 Before Start

이분 탐색을 사용하여 인출 금액의 최솟값을 구해야 하는 문제였다.

이번 문제는 이분 탐색을 사용하여 최솟값을 도출해야 하는 문제였다.
오랜만에 이분 탐색을 복습할 겸 문제를 골랐지만, 결국 답안의 도움을 받아야 했다.

✒️ Design Algorithm

이분 탐색의 범위를 먼저 지정한 후에, 인출 횟수를 구해야 한다.

N 일 간 지출 금액을 하나의 List 에 저장하고, 임의의 금액 K 을 설정한다.
그 후 보유 금액이 지출 금액보다 크다면 그냥 돈을 차감시켜도 괜찮지만,
만약 보유 금액이 지출 금액보다 적다면 K 원을 통장에서 출금해야 한다.

인출 횟수가 M 번을 넘겼다면, 필요 이상으로 인출한 것이므로 인출 금액을 올리고,
그렇지 않다면 통장에서 인출을 너무 적게 한 것이므로 인출 금액을 줄여야 한다.

또한, 인출 금액이 지출 비용보다 작다면 아무리 인출을 해도 비용을 지불할 수 없다.

왜냐하면 금액이 부족할 경우 잔금을 모두 통장에 넣고, 다시 K 원을 출금시키는데,
K 원이 인출 비용보다 작아져버리면 해당 비용을 절대로 지불할 수 없기 때문이다.

여기까지는 이해가 잘 갔다. 그래서 이를 토대로 코드를 작성했는데...

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline

N, M = map(int, read().split())
costs = [int(read()) for _ in range(N)]

# 인출 금액이 최대 비용보다는 커야 하므로, 시작 지점을 설정.
start, end = max(costs), 10000
while start < end:
    # 인출할 금액 k원을 중간 값으로 설정.
    K = (start + end) // 2
    count, current = 0, 0
    for cost in costs:
        # 보유한 돈이 지출 금액보다 적을 경우를 판별
        if current < cost:
            current = K
            count += 1
        current -= cost
    # 더 자주 인출할 경우, 금액이 작다는 의미.
    if count >= M:
        start = K + 1
    # 자주 인출하지 않았을 경우, 금액이 크다는 의미.
    else:
        end = K - 1

print(end)

탐색 과정에서의 문제는 없었으나, 결과를 도출하는 과정이 잘못되었다.

결과를 도출된 중간값인 K 가 아닌 end 로 설정한 것이 원인이었다.
따라서 정답을 다시 K 로 수정하고, 인출 횟수 코드를 살짝 수정하였다.

✅ Correct Code

import sys

read = sys.stdin.readline
N, M = map(int, read().split())
costs = [int(read()) for _ in range(N)]

# 인출 금액이 최대 지출 비용보다는 커야 하므로, 시작 지점을 지출 비용의 최댓값으로 설정.
# 지출 비용의 총합보다는 인출 금액이 작아야 하므로, 끝 지점은 지출 비용의 총합으로 설정.
start, end = max(costs), sum(costs)

while start <= end:
    K = (start + end) // 2
    # 처음에는 1회 인출을 무조건 해야 하므로, 이를 적용
    count, current = 1, K
    for cost in costs:
        # 현재 보유 금액이 지출 비용보다 더 적을 경우,
        # K원을 새롭게 꺼내어 지갑에 충전시켜야 함.
        if current - cost < 0:
            current = K
            count += 1
        current -= cost
    # 만약 인출 횟수가 많다면 인출 금액 상향
    if count > M:
        start = K + 1
        continue
    # 그렇지 않다면 금액 범위를 낮추고, 정답을 추출함.
    end = K - 1

print(K)