풍선
전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.
풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다.
각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000)
다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 DA, B로부터 떨어진 거리 DB (0 ≤ DA, DB ≤ 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σi Ki ≤ A+B.
입력의 마지막 줄에는 0이 세 개 주어진다.
출력
각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다. 이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.
풀이
이 문제는 각 테스트 케이스에 대하여 그 안의 거리 정보에 따라서 가장 최솟값을 출력하는 문제입니다. 정보마다 하나씩 출력할 필요가 없으므로 정렬을 잘 이용해서 답을 구할 수 있습니다.
중요한 것은 정렬 기준인데요. 거리의 차이가 작은 것을 먼저 해결하면 뒤의 거리차가 큰 정보에서 최솟값을 구할 수 없게 됩니다. 예를 들어 가장 먼저 거리차가 동일한 정보가 있어서 아무 풍선이나 주게 되면, 뒤에서 풍선이 모잘라 최솟값을 구할 수 없는 것입니다. 그래서 거리차가 큰 정보들 순서대로 해결해야 최솟값을 구할 수 있습니다.
정렬한 후, 기본적으로 거리가 더 짧은 풍선의 방으로 가서 풍선을 채우면 됩니다. 여기서 이제 예외상황들을 살펴보겠습니다.
거리가 더 짧지만 풍선의 개수가 모자르는 경우에는 다른 풍선을 모자르는 만큼 채워야겠죠. 그리고 거리가 동일한 경우에는 아무풍선이나 채우면 됩니다. 풍선이 모자르는 경우는 없으니까요.
import sys
input = sys.stdin.readline
while True:
n, a, b = map(int, input().split())
if n == a == b == 0:
break
else:
result = 0
# 거리의 차가 큰 값을 기준으로 정렬
info = sorted([list(map(int, input().split())) for _ in range(n)], key= lambda x : -abs(x[1]-x[2]))
for i in info:
balloon, dis_a, dis_b = i[0], i[1], i[2]
# b가 더 짧다면
if dis_a > dis_b:
# 풍선이 넉넉하면
if b >= balloon:
b -= balloon
result += dis_b*balloon
# 풍선이 모자르면
else:
result += dis_b * b + dis_a * (balloon - b)
a -= (balloon - b)
b = 0
# a가 더 짧다면
elif dis_b > dis_a:
# 풍선이 넉넉하면
if a >= balloon:
a -= balloon
result += dis_a * balloon
# 풍선이 모자르면
else:
result += dis_a * a + dis_b * (balloon - a)
b -= (balloon - a)
a = 0
# 거리차가 같으면 풍선 갯수만큼 아무 거리나 더함
else:
result += dis_a * balloon
print(result)
