[백준/6236] 용돈 관리 | 이진 탐색 트리 | 분할 | 파이썬

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

6236번: 용돈 관리

이진 탐색 / 이진 탐색 트리를 공부하고 첫 활용 문제를 풀어봤다.

이 문제가 왜 이진 탐색이냐면 

N일 동안 사용하려고 계획한 금액에 맞게 최소 K 값을 구해야 하는데, 이때 K원은 M번에 맞춰서 출력이 해야 하기 때문에 분할 개념으로 최소 K가 나올 때까지 탐색을 하기 때문이다.

분할(partition)

분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다.

집합의 분할이란 공집합이 아닌 집합 X를 서로소인 부분집합 Y1, Y2..로 나누는 것이다.

• 집합 Y들을 모으면 집합 X가 된다.
• X의 원소들은 서로소이며, 교집합이 없다.

이 문제에서는 각각 일(day)별로 원소들이 있고 이들을 M번 분할하여 최소 K를 찾는다.

입력 예제를 분할의 예로 들면 100 400 / 300 100 / 500 / 101 / 400 이렇게 총 5번의 집합으로 분할이 되고, K는 500이다.

 

알고리즘_이진탐색

이진탐색을 위해서 왼쪽 노드와 오른쪽 노드를 정해준다.

K의 최소값은 데이터 하나 값보다는 크거나 같아야 하고, 최대값은 M=1일 때 즉 한 묶음일 때이므로, 예산안의 총합이다.

이렇게 왼쪽 노드와 오른쪽 노드를 설정한 뒤, 예산안을 for문으로 하나씩 비교한다.

 

만약 가진 돈이 예산보다 부족하면 인출을 해서 사용해야 하기 때문에 partition의 개수를 세어준다. 아닐 경우에는 이미 가지고 있는 돈(day_charge)에서 예산을 빼주어 계산한다.

 

partition의 개수를 다 세었다면 m과 비교하고, 현재 노드를 예산안의 최대값과 비교하여 최소 K를 찾아준다.

현재 기준값(mid)이 m번 안에 다 해결이 안되면 기준값을 수정하여 재탐색한다.

---

최종 코드

n,m = map(int, input().split())
budget = [int(input()) for _ in range(n)]
# 인출할 최소 금액 : left, 최대금액 : right
lt = min(budget)
rt = sum(budget)

while lt <= rt :
    k = (lt + rt) // 2
    day_charge = 0
    m_cnt = 0
    
    for i in budget :
        # 가진 돈이 예산 보다 부족하면 인출
        if day_charge < i :
            day_charge = k 
            m_cnt += 1
        day_charge -= i
        
    # m 만큼만 출력 가능 or 기줁값이 max 값보다 작으면 mid 값 증가, 재탐색
    if m_cnt > m or k < max(budget) : 
        # 기준값을 늘려서 재탐색
        lt = k + 1
    else:
        # 기준값을 감소하여 재탐색
        rt = k - 1
        ans = k
print(ans)

 

알게된 점

• 이진탐색을 문제 해결에 사용하는 방법
• 이진탐색트리 탐색 알고리즘