[백준][파이썬] 6236번 용돈 관리

 

꽤나 곤란한 문제였다......

일단 문제 이해부터 막혀 블로그랑 질문 게시판을 많이 참고해야 했다.

그리고도 놓치는 조건들이 있어 열심히 써내려 가보며 문제를 풀었다.

이 포스팅에는 내가 헷갈린 모든 부분들을 담아보려 한다.

 

6236번 : 용돈 관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 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를 출력한다.

링크

6236번: 용돈 관리 (acmicpc.net)

6236번: 용돈 관리

 

 

문제 이해

우선 문제 이해부터 막힌... 여러 블로그를 찾아보면 이런 문제라고 나오는 한 줄의 문구가 있다.

" N개의 수에서 합이 K 이하인 M개의 그룹으로 묶을 때의 최솟값 K 찾기 "

위 문구를 이해하기 위해서는 번역 전 원문 문제를 참고하면 이해에 도움이 된다.

글 읽기 - 6236 용돈 관리) 문제 원문을 찾아 번역해보았습니다 (acmicpc.net)

 

정리해보면 이렇다. 

돈을 먼저 K원만큼 통장에서 인출한다. 그럼 내 지갑에는 현금으로 K원이 있는 것이다. 그 후에 사용할 금액(입력되는 값들)을 소비한다. 그럼 내 지갑에서 돈이 계속 빠져나갈 것이다. 그렇게 소비하다 보면 돈이 부족할 것이다. 그때 나에게 남아 있는 돈은 통장에 다시 넣어버리고(내 손에서 떠난 돈, 신경X) 새로 K원만큼만 다시 통장에서 인출한다. 그럼 다시 내 지갑에는 K원만큼이 생길 것이다. 이렇게 소비, 인출, 소비, 인출을 반복하여 끝났을 때 인출 횟수가 M번이 되어야 한다.

그럼 백준의 예제를 통해 다시 풀어보겠다.

(1) 500원 인출
100원 사용 → 400원 남음 → 400원 사용 → 0원 남음 → 다음에 낼 돈이 없다.
(2) 500원 인출
300원 사용 → 200원 남음 → 100원 사용 → 100원 남음 → 다음에 낼 돈이 부족하다.
(3) 남은 100원 입금, 500원 인출
500원 사용 → 0원 남음 → 다음에 낼 돈이 없다.
(4) 500원 인출
101원 사용 → 399원 남음 → 다음에 낼 돈이 부족하다.
(5) 남은 399원 입금, 500원 인출
400원 사용 → 100원 남음
※ 끝! 총 5번 인출하게 되니 500원이 정답되겠다.

 

 

접근 방법

1. n,m 값을 입력 받고 이용할 금액은 list로 입력 받는다.
2. 인출 금액의 최솟값을 구해야 하므로 매개변수 탐색을 고려한다
3. start, end, mid 값을 설정한다.
4. mid 값만큼 인출할 때 인출해야 하는 횟수(count)를 센다. 
   1. count > m 혹은 mid < max(money) 인 경우, 인출금액을 높여야 하므로 start 값을 증가시켜 구간을 다시 설정한다.
   2. count <= m 인 경우, 인출 금액을 낮춰야 하므로 end 값을 감소시켜 구간을 다시 설정한다.
5. 위 두 단계를 start가 end를 역전할 때까지 반복한다.
6. 이후 인출 금액의 최솟값인 mid 값을 출력한다.

매개변수 탐색 참고 자료 : [알고리즘] 이진 탐색(Binary Search) + 매개변수 탐색(Parametric Search) — y-seo의 딩코 기록들 (tistory.com)

[알고리즘] 이진 탐색(Binary Search) + 매개변수 탐색(Parametric Search)

 

 

 풀이

1. start, end 값을 어떻게 지정해주어야 할지

start, end = max(money), sum(money)

start 값은 가장 적게 인출할 수 있는 금액인 max(money)로 설정하고, end 값은 가장 많이 인출할 수 있는 금액인 sum(money)로 설정한다. 물론 문제 조건은 (1 ≤ 금액 ≤ 10000) 이므로 1, 10000으로도 설정은 가능하나 범위를 최대한 줄여주었다.

max(money)인 이유는 예시로 설명하면 다음과 같다. 만약 200원씩 인출할건데 하루는 내가 500원을 써야 한다고 가정해보자. 내가 돈이 부족할 때는 남은 금액을 다시 통장에 입금하고 200원만을 인출할 것이기 때문에 절대로 주어진 소비를 할 수가 없다... 

sum(money)인 이유는 딱 1번의 인출로 소비가 모두 가능하기 때문이다.

2. count를 어떻게 세어줄지

for i in money: 
        if charge - i < 0: #부족해서 다시 인출
            count += 1
            charge = mid
        charge -= i #사용한 만큼 차감

count는 인출하는 횟수이므로 내가 정한 인출한 금액(mid)을 우선 잔액의 의미를 가진 charge 변수에 동일하게 저장한다. 이후에 소비를 하려고 했는데, charge - 소비 금액(i) < 0 이라 음수가 나오면? 다시 인출해야 하므로 count 값을 1 늘려주고 charge는 다시 mid만큼 채워준다. 이후 소비를 위해 charge에서 i를 빼어 남는 돈을 계산한다. 위 과정을 i가 끝날 때까지 반복하여 count를 계산한다.

 

 

 

 전체코드

import sys

n, m = map(int,sys.stdin.readline().split())
money = []
for i in range(n): #사용 금액 입력 받기
    money.append(int(sys.stdin.readline()))

start, end = max(money), sum(money)

while start <= end: #매개변수 탐색
    mid = (start + end) // 2 #인출 금액
    charge = mid #인출 금액
    count = 1
    for i in money: 
        if charge - i < 0: #부족해서 다시 인출
            count += 1
            charge = mid
        charge -= i #사용한 만큼 차감
    if count > m: #인출 액수 증가 필요
        start = mid + 1
    else: #인출 액수 감소 필요
        end = mid - 1
print(mid)