백준 6236 용돈 관리 Python 3

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

6236번: 용돈 관리

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ6236.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_withdrawal(money, M):
    left = max(money)
    right = max(money)*len(money)
    answer = right
    while left <= right:
        mid = (left+right)//2
        wallet = 0
        cnt = 0
        for m in money:
            if m <= wallet:
                wallet -= m
            else:
                if cnt >= M: break
                wallet = mid - m
                cnt += 1
        else:
            answer = min(answer, mid)
            right = mid-1
            continue
        left = mid+1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
money = list()
for _ in range(N):
    money.append(int(input()))
print(get_withdrawal(money, M))

---

풀이 과정

풀이 시간 22분

통장에서 K원을 M번만 인출해서 하루하루 돈을 사용할 수 있도록 하는 최소 금액 K를 구하는 문제이다.

이때, K원보다 적은 돈을 쓴 다음날 남은 금액으로 사용 가능하다면 돈을 새로 인출하지 않는다. 반대로 남은 금액이 다음 날 사용할 금액보다 적은 경우에는 남은 돈은 무시하고 K원을 인출해서 사용하는 것이 문제의 포인트다.

따라서 필요한 최소 금액 K원을 구하는 이분 탐색 알고리즘을 짤 수 있다.

import sys
def get_withdrawal(money, M):
	#인출 금액 범위 초기화 -> 하루에 사용할 금액 중 최대 금액보다 크거나 같고, N*max(money)보다 작거나 같아야 한다
    left = max(money)
    right = max(money)*len(money)
    
    #최대 금액으로 K원 초기화
    answer = right
    
    #이분 탐색
    while left <= right:
    	#K원을 mid로 가정
        mid = (left+right)//2
        #현재 가지고 있는 돈
        wallet = 0
        #인출 횟수
        cnt = 0
        
        for m in money:
        	#현재 가지고 있는 금액이 사용할 금액보다 크거나 같은 경우,
            if m <= wallet:
            	#통장에서 돈을 인출하지 않고 현재 가지고 있는 돈으로 소비한다
                wallet -= m
                
            #돈이 부족한 경우,
            else:
            	#인출 횟수가 초과된 경우, mid 값을 조정해야 한다
                if cnt >= M: break
                #인출 횟수가 초과되지 않은 경우, 인출 후 소비한다
                wallet = mid - m
                cnt += 1
        #mid원 인출 금액으로 모든 소비가 이뤄진 경우,
        else:
        	#answer값 갱신
            answer = min(answer, mid)
            #최소의 K원을 찾기 위해 right 범위를 줄인다
            right = mid-1
            continue
        #mid원 인출 금액으로 모든 소비가 불가능한 경우, mid 값을 늘리기 위해 left 범위를 늘린다
        left = mid+1
    return answer

input = sys.stdin.readline
N, M = map(int, input().split())
money = list()
for _ in range(N):
    money.append(int(input()))
print(get_withdrawal(money, M))

#시간복잡도 = O(log n), 공간복잡도 = O(n)