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

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

6236번: 용돈 관리

 

분할(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)

 

알게된 점

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