[백준] 4716번 풍선

문제 설명

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

문제 풀이

• 정렬 및 그리디한 접근을 이용해 풀이하였다.
• 문제에서 중요한 정렬의 조건의 경우 A와의 거리, B와의 거리 차이를 기준으로 내림차순 정렬을 진행하여 차이가 큰 것부터 가까운 풍선을 우선적으로 나르면 된다.

소스 코드 (JAVA)

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Team implements Comparable<Team>{
        int cnt, da, db;

        public Team(int cnt, int da, int db) {
            this.cnt = cnt;
            this.da = da;
            this.db = db;
        }

        @Override
        public int compareTo(Team o) {
            return Math.abs(o.da - o.db) - Math.abs(this.da - this.db);
        }
    }

    static int N, A, B;
    static List<Team> teamList = new ArrayList<>();

    public static void solve() throws IOException {
        Collections.sort(teamList);

        int result = 0;
        for (Team cur : teamList) {
            // B를 넣어줘야 하는 경우
            if (cur.db < cur.da) {
                // 잔여분이 있을 경우
                if ( cur.cnt <= B ) {
                    result += cur.cnt * cur.db;
                    B -= cur.cnt;
                } else {
                    result += B * cur.db;
                    cur.cnt -= B;
                    B = 0;
                    result += cur.cnt * cur.da;
                    A -= cur.cnt;
                }
            }
            // A를 넣어줘야 하는 경우
            else {
                if ( cur.cnt <= A ) {
                    result += cur.cnt * cur.da;
                    A -= cur.cnt;
                } else {
                    result += A * cur.da;
                    cur.cnt -= A;
                    A = 0;
                    result += cur.cnt * cur.db;
                    B -= cur.cnt;
                }
            }
        }

        bw.write(result + "\n");
    }



    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            teamList = new ArrayList<>();
            if (N == 0 && A == 0 && B == 0) break;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int cnt = Integer.parseInt(st.nextToken());
                int da = Integer.parseInt(st.nextToken());
                int db = Integer.parseInt(st.nextToken());
                teamList.add(new Team(cnt, da, db));
            }
            solve();
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        bw.flush();
    }
}