[BaekJoon] 2786 상근이의 레스토랑 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int foodCount;
    static long[] orderPricePrefixSum;
    static int[] gapsOfFirstOrderPriceAndOrderPrice;
    static int[] minFirstOrderPrices;
    static Food[] foods;

    static void input() {
        Reader scanner = new Reader();

        foodCount = scanner.nextInt();
        orderPricePrefixSum = new long[foodCount + 1];
        gapsOfFirstOrderPriceAndOrderPrice = new int[foodCount + 1];
        minFirstOrderPrices = new int[foodCount + 1];
        foods = new Food[foodCount + 1];
        foods[0] = new Food(0, 0);

        for (int foodIdx = 1; foodIdx <= foodCount; foodIdx++) {
            foods[foodIdx] = new Food(scanner.nextInt(), scanner.nextInt());
        }
    }

    /*
     * 1. 1개의 음식을 주문했을 때의 최소 비용 = Ai의 최솟값
     * 2. N개의 음식을 주문했을 때의 최소 비용 = Bi의 합 + (Ai - Bi)의 최솟값
     *      - Ai = Bi + x ==> x = Ai - Bi
     *      - x + Bi = Ai - Bi + Bi = Ai
     *      - 즉, (Ai - Bi)의 최솟값을 더해주면 한 음식은 처음 주문한 가격으로 계산되고 나머지 음식은 나중에 주문한 가격으로 계산된다
     *      -> 이 값을 구하기 위해 Bi의 누적합을 더해놔야 한다
     * 3. 2 ~ (N - 1)개의 음식을 주문했을 때의 최소 비용
     *      a. x개의 음식을 샀을 때, 산 음식 중 최소 Ai값을 가지는 음식을 포함하는 경우
     *          - x개의 음식을 산 경우의 Bi의 누적합 + 구매한 음식 중 (Ai - Bi)의 최솟값
     *              - Ai의 최솟값을 포함하고 있다면 그 음식을 처음 주문하고 나머지를 이후에 주문하면 최소 비용이 될 것이다
     *      b. x개의 음식을 샀을 때, 산 음식 중 최소 Ai값을 가지는 음식을 포함하지 않는 경우
     *          - 구매한 음식 중 최소 Ai값을 가지는 음식을 포함하지 않았기 때문에 최소 Ai값을 가지는 음식을 포함시켜 해당 음식을 처음 주문하고 (x - 1)개의 음식을 이후에 주문한다
     *          - 즉, x개 중 x - 1개의 음식값 누적합 + 최소 Ai
     *      - 그러나 각 경우에서 꼭 해당 방법이 최소라고 장담할 수 없기 때문에 두 방법 모두 적용하여 그 중 더 작은 값이 최솟값이 된다!
     */
    static void solution() {
        Arrays.sort(foods);
        calculatePrefixSumAndGapAndMinFirstOrderPrice();
        System.out.print(findMinOrderPrice());
    }

    static String findMinOrderPrice() {
        int minGap = Integer.MAX_VALUE;
        StringBuilder answer = new StringBuilder();
        for (int foodIdx = 1; foodIdx <= foodCount; foodIdx++) {
            if (minGap > gapsOfFirstOrderPriceAndOrderPrice[foodIdx]) {
                minGap = gapsOfFirstOrderPriceAndOrderPrice[foodIdx];
            }
            long sum = Math.min(orderPricePrefixSum[foodIdx - 1] + minFirstOrderPrices[foodIdx],
                    orderPricePrefixSum[foodIdx] + minGap);
            answer.append(sum).append('\n');
        }
        return answer.toString();
    }

    static void calculatePrefixSumAndGapAndMinFirstOrderPrice() {
        int minFirstOrderPrice = Integer.MAX_VALUE;
        for (int foodIdx = 1; foodIdx <= foodCount; foodIdx++) {
            orderPricePrefixSum[foodIdx] = orderPricePrefixSum[foodIdx - 1] + foods[foodIdx].orderPrice;
            gapsOfFirstOrderPriceAndOrderPrice[foodIdx] = foods[foodIdx].firstOrderPrice - foods[foodIdx].orderPrice;

            if (foods[foodCount - foodIdx + 1].firstOrderPrice < minFirstOrderPrice) {
                minFirstOrderPrice = foods[foodCount - foodIdx + 1].firstOrderPrice;
            }
            minFirstOrderPrices[foodCount - foodIdx + 1] = minFirstOrderPrice;
        }
    }

    static class Food implements Comparable<Food> {
        int firstOrderPrice;
        int orderPrice;

        public Food(int firstOrderPrice, int orderPrice) {
            this.firstOrderPrice = firstOrderPrice;
            this.orderPrice = orderPrice;
        }

        @Override
        public int compareTo(Food o) {
            return orderPrice - o.orderPrice;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}