백준 - 용돈관리 / Silver 2 / 6236번 / Python

문제 📋

백준 - 용돈관리

풀이 📝

import sys


n, m = map(int, sys.stdin.readline().split())

moneys = [int(sys.stdin.readline()) for _ in range(n)]


def simulate(k, money_list):  # M번의 인출 횟수 내에 N일 동안 생활이 가능한 지 시뮬레이션.
    if max(money_list) > k:
        return False
    pocket = k
    cnt = 1
    for money in money_list:
        if pocket < money:
            pocket = k
            cnt += 1
        pocket -= money
    if cnt > m:
        return False
    return True


def binary_search(money_list):  # k의 최솟값을 찾기 위한 이분탐색.
    start = min(money_list)
    end = sum(money_list)
    target = end

    while start <= end:
        mid = (start + end) // 2

        if simulate(mid, money_list):
            end = mid - 1
            target = mid  # 현재 값보다 작은 값을 탐색할 때만 target에 저장.
        else:
            start = mid + 1
    return target


print(binary_search(moneys))

처음에 문제를 이해하는데 조금 어려움이 있었던 문제였다.
최종적으로 이해한 바로는 다음과 같다.

1. 현재 남은 금액으로 오늘을 보낼 수 있으면 보내고 그 금액만큼 차감.

2. 현재 남은 금액으로 오늘을 보낼 수 없으면 남은 금액 다시 넣고 K원 출금.

3. K원으로 오늘을 보낼 수 없으면 여러번 출금하는게 아닌 K원의 금액을 높인다.
   -> 금액이 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다고 했는데
   K원 자체가 모자란 금액이면 해당 로직을 무한반복하기 때문에 K원 금액 자체를 높여야 한다.

위와 같은 로직을 simulate() 함수에 구현하여 K원을 인자로 넣었을 때 인출을 M번내로 할 수 있는지 체크해주었다.

최종적으로 이 문제에서 찾아야 하는건 인출을 M번내로 할 수 있는 K값 중 최솟값을 찾는 것이다.
따라서 K의 값의 범위를 정하고 해당 범위를 탐색하여 조건을 만족하는 가장 작은 K값을 찾아야 하는데 금액의 최대 크기가 10,000 이므로 완전탐색 시 최악의 경우 10,000번 탐색을 진행해야 한다.

그러나 문제의 입력에서 N의 크기가 100,000이고 simulate() 함수에서 이미 O(N) 탐색을 하기 때문에 그렇게 되면 시간 초과가 될 확률이 높다.

따라서 K의 값 탐색에 Binary Search을 활용하여 시간복잡도를 O(logN)으로 줄여서 문제를 해결할 수 있었다.

PS. 해당 소스를 함수로 만들지 않고 그냥 구현했을 경우 Python3로 시간 초과가 났는데 함수로 만들어서 실행시키니 Python3으로 통과하였다.
해당 문제는 컴퓨터 구조의 명령어와도 관련되어 있는데
요약하면 반복문 내에 전역변수를 사용하지 않으면 실행 시간에서 이점이 있을 수도 있다.

자세한 내용은 다음 포스팅을 참고하면 좋을 듯 하다.
https://8iggy.tistory.com/155