백준|4716번|풍선

문제 설명

N개의 방에 풍선을 필요한 개수만큼 갖다 줘야 하고 풍선은 서로 다른 위치에 있는 방 A, B에 있습니다. 이때 각 방에 필요한 만큼의 풍선을 모두 갖다 줄 때 움직여야 하는 최소한의 이동 거리를 구하는 문제입니다.

작동 순서

1. 방의 개수와 A, B 방에 있는 풍선의 개수를 입력받습니다.
2. 각 방 별로 필요한 풍선의 개수와 A, B와의 거리를 입력받습니다.
3. 각 방에 필요한 풍선을 최소한의 이동으로 모두 갖다 주기 위해서는 A와의 거리, B와의 거리 간의 차이가 큰 방일수록 최대한 더 가까운 방에서 가져오는 것이 이득이므로 두 거리 간의 차이를 기준으로 힙에 삽입합니다. 이때 두 거리 간의 차이를 제곱하여서 부호의 영향을 받지 않게 해줍니다.
4. 두 거리 간의 차이가 큰 방에서부터 최대한 가까운 방에서 풍선을 가져오고 만약 더 가까운 방에 풍선이 없으면 먼 방에서 풍선을 가져옵니다.
5. 위의 과정에서의 이동거리를 출력합니다.
6. 0,0,0이 입력될 때까지 1~5번을 반복합니다.

소스코드

import sys
import heapq

while True:
    N, A, B = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    balloon = [A, B]
    dist = [[0, 0] for _ in range(N)]
    heap = []
    total = 0

    for i in range(N):
        K, dA, dB = map(int, sys.stdin.readline().split())
        dist[i] = [dA, dB]
        diff = (dA-dB)**2
        heapq.heappush(heap, [-diff, K, i])

    while heap:
        d, k, idx = heapq.heappop(heap)
        biggerB = dist[idx][0] < dist[idx][1]
        if balloon[not biggerB] >= k:
            balloon[not biggerB] -= k
            total += k*dist[idx][not biggerB]
        elif balloon[not biggerB] > 0:
            k -= balloon[not biggerB]
            total += balloon[not biggerB]*dist[idx][not biggerB]
            balloon[not biggerB] = 0
            total += k*dist[idx][biggerB]
            balloon[biggerB] -= k
        else:
            total += k * dist[idx][biggerB]
            balloon[biggerB] -= k
    print(total)