https://www.acmicpc.net/problem/4716
4716번: 풍선
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개
www.acmicpc.net
문제
전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.
풍선은 방 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에서 팀으로 이동하는 거리만 포함한다.
아이디어
방 A, B에 풍선이 있고 각 팀마다 방마다의 거리와 필요한 풍선 수가 주어진다. 이때 최소로 이동하는 거리를 구해야 한다.
여기서 가장 중요한 것은 방과의 거리의 차가 큰 팀이다. 왜냐? 방 a나 b의 거리가 같거나 조금밖에 차이가 안 나면 어느 방을 가던 상관이 없다.
따라서 거리의 차를 내림차순으로 정렬한 뒤, 거리차가 큰 팀을 먼저 처리하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
private static class Team implements Comparable<Team> {
int count;
int distanceA;
int distanceB;
public Team(int count, int distanceA, int distanceB) {
this.count = count;
this.distanceA = distanceA;
this.distanceB = distanceB;
}
private int getDiff() {
return Math.abs(distanceA - distanceB);
}
@Override
public int compareTo(Team o) {
return Integer.compare(o.getDiff(), getDiff());
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
while (true) {
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
if (n == 0) break;
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
Team[] teams = new Team[n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
teams[i] = new Team(Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()));
}
Arrays.sort(teams); // 방 사이의 거리의 차가 큰 것부터 풍선 나르기
int answer = 0;
for (Team t : teams) {
if (t.distanceA < t.distanceB) { // a가 가까울 경우 방 a에서 풍선 나르기
if (a >= t.count) {
answer += t.count * t.distanceA;
a -= t.count;
} else { // 풍선이 부족하다면 나머지는 b에서
answer += a * t.distanceA;
t.count -= a;
a = 0;
answer += t.count * t.distanceB;
b -= t.count;
}
} else { // b가 가까울 경우 방 b에서 풍선 나르기
if (b >= t.count) {
answer += t.count * t.distanceB;
b -= t.count;
} else { // 풍선이 부족하다면 나머지는 a에서
answer += b * t.distanceB;
t.count -= b;
b = 0;
answer += t.count * t.distanceA;
a -= t.count;
}
}
}
sb.append(answer).append("\n");
}
System.out.print(sb);
}
}
