졍's 기술 블로그

용돈 관리

티어 : Silver 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 이분 탐색, 매개 변수 탐색

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

예제 입출력

Algorithm

이진 탐색 - 반복
mid : 한 번에 뺄 수 있는 금액 (K)
for문 안에서의 조건
➝ 잔고가 오늘 예산보다 적으면 인출
mid 값 갱신의 조건
➝ 출금 횟수가 M보다 커지거나 mid값이 예산의 최댓값보다 작은 경우 mid를 키워서 재탐색
➝ 출금횟수가 M보다 작거나 같으면 mid 줄여서 재탐색 (최솟값 갱신)

Code

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
budget = []
for _ in range(N):
    budget.append(int(input()))

# start, end 초기화
start = min(budget)
end = sum(budget)

# 이진 탐색
answer = 0
while start <= end:
    
    mid = (start + end) // 2
    
    balance = 0
    count = 0
    for today in budget:
        
        # 오늘 예산보다 잔고가 부족하면 인출
        if balance < today:
            balance = mid
            count += 1
        
        balance -= today
    
    
    # 인출 횟수가 M보다 많거나 mid가 예산의 최댓값보다 작으면 mid값 증가시켜 다시 탐색
    if count > M or mid < max(budget):
        start = mid + 1
    else: # 인출 횟수가 M과 같거나 M보다 적으면 mid값 감소시켜 다시 탐색
        end = mid - 1
        answer = mid

print(answer)

메모리: 33688 KB
시간: 540 ms