[백준] 4716번 풍선 Java

문제 링크

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

알고리즘: 그리디

문제

전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.

풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다.

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

풀이

이동 거리의 최솟값을 출력하려면 풍선 분배의 우선순위를 생각해야 한다.
1. 각 팀에서 방 A 거리와 방 B 거리의 차이값이 큰 값.

차이값을 내림차순으로 정렬해주고 A 방과 B 방중 어느 방이 더 가까운지 판단해서 우선적으로 풍선을 분배해주면 이동 거리의 최솟값을 출력할 수 있다.

소스 코드

import java.io.*;
import java.util.*;

class TeamInfo implements Comparable < TeamInfo > {
    int bc,
    a,
    b,
    dif;
    char pb; //우선순위 풍선
    public TeamInfo(int bc, int a, int b, int dif, char pb) {
        this.bc = bc;
        this.a = a;
        this.b = b;
        this.dif = dif;
        this.pb = pb;
    }

    public int compareTo(TeamInfo t) {
        int df = t.dif - this.dif;
        if (df > 0) return 1;
        if (df < 0) return -1;
        return 0;
    }
}

public class Main {
    static int N, A, B,ans;
    static TeamInfo team[];
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            ans = 0;
            team = new TeamInfo[N];
            if(N+A+B == 0) {
                break;
            }
            for (int i = 0; i < N; i++) {
                StringTokenizer sti = new StringTokenizer(br.readLine());
                int tbc = Integer.parseInt(sti.nextToken());
                int ta = Integer.parseInt(sti.nextToken());
                int tb = Integer.parseInt(sti.nextToken());
                if (ta - tb >= 0) {
                    team[i] = new TeamInfo(tbc, ta, tb, ta - tb, 'B');
                } else {
                    team[i] = new TeamInfo(tbc, ta, tb, tb - ta, 'A');
                }
            }
            
            Arrays.sort(team);
            for (int i = 0; i < N; i++) {
                if (team[i].pb == 'B') {
                    if (B - team[i].bc >= 0) {
                        ans += team[i].b * team[i].bc;
                        B = B - team[i].bc;
                    } else {
                        int leftA = team[i].bc - B;
                        ans += B * team[i].b + leftA * team[i].a;
                        A = A - leftA;
                        B = 0;
                    }
                } else {
                    if (A - team[i].bc >= 0) {
                        ans += team[i].a * team[i].bc;
                        A = A - team[i].bc;
                    } else {
                        int leftB = team[i].bc - A;
                        ans += A * team[i].a + leftB * team[i].b;
                        B = B - leftB;
                        A = 0;
                    }
                }
            }
            System.out.println(ans);
        }
    }
}