백준 4716번 - 풍선

문제

백준 4716번 - 풍선

아이디어

최종 거리가 최소가 되기 위해서는 각 팀이 받을 풍선을 최대한 가까운 방에서 가져와야 하므로 그리디하게 접근하여 해결한다.

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BJ_4716 {
    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 (n == 0 && a == 0 && b == 0) {
                break;
            }

            int[][] arr = new int[n][3];

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
                arr[i][2] = Integer.parseInt(st.nextToken());
            }

            // 1
            Arrays.sort(arr, Comparator.comparingInt(o -> Math.abs(o[1] - o[2])));

            // 2
            int ans = 0;
            for (int i = n - 1; i >= 0; i--) {
                int k = arr[i][0];
                int da = arr[i][1];
                int db = arr[i][2];

                // 3
                if (da < db) {
                    if (a - k > 0) {
                        ans += k * da;
                        a -= k;
                    }
                    else {
                        ans += a * da;
                        ans += (k - a) * db;
                        a = 0;
                    }
                }
                else {
                    if (b - k > 0) {
                        ans += k * db;
                        b -= k;
                    }
                    else {
                        ans += b * db;
                        ans += (k - b) * da;
                        b = 0;
                    }
                }
            }

            sb.append(ans).append("\n");
        }
        System.out.print(sb);
    }
}

1

• 정렬 방식이 문제 해결의 핵심으로, 두 방과의 거리 차이를 기준으로 정렬한다.
• 거리 차이가 크다는 것은 한 방이 확실히 더 가깝다는 의미이므로, 그 방에서 풍선을 가져오도록 한다.

2

• 거리 차이가 큰 팀부터 먼저 계산 되도록 한다.

3

• 더 가깝게 있는 방에서 풍선을 가져오는 계산을 한다.
• 기존 A개 또는 B개 풍선에서 차감되어도 풍선이 남으면 단순히 계산하고, 풍선이 부족하면 부족한 만큼 반대편에서 추가 풍선을 가져오도록 한다.

예상 시간 복잡도

• T : 테스트 케이스 개수
• 예상 시간 복잡도 : O(T * NlogN)