백준 6236 용돈 관리

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

6236번: 용돈 관리

📌 해결순서

정말정말정말 오래걸렸다 얼마동안 붙잡고 있었는지에 대한건 기억도 나지 않는다..

이 문제를 오래붙잡고 있었던 이유가 있는데, 

하루에 돈을 두번 뽑을 수 있다고 생각하고 문제에 접근했기 때문이다

예를 들어서 

뽑는 금액이 300이고 첫날 사용하는 금액이 500 이면 돈을 두번 뽑아서 600을 만들고, cnt +=2 해주고 시작하면 되지 않을까 했지만 문제에서는

"모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다" 라는 조건이 있기 때문에 위의 예시는 300을 뽑으면 200이 모자라기 때문에 다시 300을 통장에 집어놓고 300을 뽑는다. 그리고, 이걸 무한반복하기 때문에 이렇게 생각하면 문제를 풀 수 없다.

또 다른 예시로

500을 뽑아서 300을 쓰고 200이 남았는데 다음날 700을 써야하는 상황이라면 남은 200에 500을 뽑아서 700을 만들면 되지 않을까 생각 했지만 이 경우에도 200을 다시 넣기 때문에 뽑고 넣고 무한반복이여서 문제를 해결 하지 못한다...

계에에에에에에에속 이 생각에서 빠져 나오지 못해서 다음 단계로 넘어가지 못했다...정말 슬펐다 😂

 

1. start 와 end 값 정하기

위의 시행착오를 통해서 start 값은 n일 동안 쓰려고 하는 값중 최댓값임을 알수 있다.

end는 만약에 돈을 1번만 뽑는다고 가정하면 돈을 뽑는 금액의 최솟값은 n일동안 쓰려고 하는 값의 합이다.

 

2. 탐색범위 줄여가기

이 탐색에서 중간값이 의미하는 것은 현재 뽑는 금액 k 를 의미한다

첫날에 돈을 k 원 뽑고 시작하므로 cnt = 1 로 탐색을 시작해준다

k원에서 사용하려고 하는 돈을 빼주고  만약 남은돈이 다음날 써야하는 돈 보다 적으면 cnt += 1 해준다.

만약 돈을 뽑는 횟수 cnt 가 m 보다 크다면 뽑는 금액이 적기 때문에 현재 중간값 보다 적은 값에 대해서 탐색을 할 필요가 없기 때문에 start = mid + 1 로 탐색범위를 줄여준다

cnt가 m 보다 작으면 돈을 뽑는 금액이 많기 때문에 현재 중간값 보다 큰 값에 대해서 탐색할 필요가 없기 때문에 end = mid - 1로 탐색범위를 줄여준다

📌 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    n, m = map(int, input().split())
    lst = [int(input()) for _ in range(n)]

    start = max(lst)
    end = sum(lst)

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

        cnt = 1
        ans = 0

        for money in lst:
            if current < money:
                cnt += 1
                current = mid
            current -= money

        if cnt > m:
            start = mid + 1
        else:
            ans = mid
            end = mid - 1

    print(ans)