문제
전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.
풍선은 방 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로부터 떨어진 거리 D_A, 방 B로부터 떨어진 거리 D_B (0 <= D_A, D_B <= 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σᵢ Kᵢ <= A+B.
입력의 마지막 줄에는 0이 세 개 주어진다.
출력
각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다. 이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.
풀이
어느 창고에서 받아야 손해가 큰지가 먼저 결정돼야 한다. 그래서 각 팀을 |distA - distB|가 큰 순서로 정렬하는 그리디가 핵심이다.
차이가 큰 팀은 한쪽 창고를 쓰지 못하면 손해가 커지므로 먼저 처리해야 한다. 정렬 후에는 더 가까운 창고에서 가능한 만큼 풍선을 주고, 부족한 만큼만 반대쪽에서 받으면 된다.
이 문제에서 단순히 "지금 더 가까운 창고에서 먼저 준다"만으로는 부족하다. 어떤 팀은 두 창고 거리 차가 거의 없지만, 어떤 팀은 한쪽 창고를 못 쓰면 총 이동 거리가 크게 늘어난다. 그래서 거리 차가 큰 팀부터 배정해야 전체 손해를 최소화할 수 있다.
코드도 바로 그 기준으로 정렬한 뒤, 각 팀에 대해 더 가까운 창고 재고를 먼저 사용한다. 재고가 부족한 경우에만 남은 수량을 반대쪽 창고에서 가져오고, 그 비용을 누적하면 된다. 핵심은 개별 팀의 최선 선택보다 처리 순서를 먼저 맞추는 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static class Ballon implements Comparable<Ballon> {
int amount, disA, disB;
Ballon(int amount, int disA, int disB) {
this.amount = amount;
this.disA = disA;
this.disB = disB;
}
@Override
public int compareTo(Ballon o) {
int diff1 = Math.abs(this.disA - this.disB);
int diff2 = Math.abs(o.disA - o.disB);
return diff2 - diff1;
}
}
static List<Ballon> ballons;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
if (A == 0 && B == 0 && N == 0) break;
ballons = new ArrayList<>();
while (N-- > 0) {
st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
int DA = Integer.parseInt(st.nextToken());
int DB = Integer.parseInt(st.nextToken());
ballons.add(new Ballon(K, DA, DB));
}
// A와 B의 거리차가 큰 순서대로 정렬
Collections.sort(ballons);
sb.append(solve(A, B)).append('\n');
}
System.out.println(sb);
}
static long solve(int A, int B) {
long ans = 0;
for (Ballon ballon : ballons) {
if (ballon.disA < ballon.disB) {
int takeA = Math.min(A, ballon.amount); // A애서 가져갈 풍선
int takeB = ballon.amount - takeA; // 모자란 만큼은 B에서 가져감
ans += (takeA * ballon.disA) + (takeB * ballon.disB);
A -= takeA;
B -= takeB;
} else {
int takeB = Math.min(B, ballon.amount);
int takeA = ballon.amount - takeB;
ans += (takeA * ballon.disA) + (takeB * ballon.disB);
A -= takeA;
B -= takeB;
}
}
return ans;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
가까운 창고부터 주면 될 것 같지만, 진짜 중요한 건 양쪽 거리 차가 얼마나 큰지다. 손해가 큰 팀을 먼저 처리하는 정렬 그리디가 정답이다.
