[BaekJoon] 15824 너 봄에는 캡사이신이 맛있단다 (Java)

1.  문제 링크

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

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 final int DIVISOR = 1_000_000_007;
    static int N;
    static int[] scoville;

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

        N = scanner.nextInt();
        scoville = new int[N];

        for(int idx = 0; idx < N; idx++)
            scoville[idx] = scanner.nextInt();
    }

    static void solution() {
        Arrays.sort(scoville);

        long[] dp = new long[N];
        dp[0] = 1;
        for(int idx = 1; idx < N; idx++)
            dp[idx] = (dp[idx - 1] * 2) % DIVISOR;

        long answer = 0;
        for(int idx = 0; idx < N; idx++)
            answer = (answer + (scoville[idx] * (dp[idx] - dp[(N - 1) - idx]))) % DIVISOR;

        System.out.println(answer);
    }

    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());
        }
    }
}

4.  접근

• 주헌고통지수는 {한 메뉴 조합에서의 스코빌 지수 최댓값 - 스코빌 지수 최솟값}으로 나타낼 수 있으므로 결국 주헌고통지수의 합은 {모든 조합 각각에서의 스코빌 지수 최댓값들의 합 - 스코빌 지수 최솟값들의 합}으로 나타낼 수 있습니다.
• 그러므로 각 메뉴들이 최댓값이 되는 경우의 수와 최솟값이 되는 경우의 수를 구하면 주헌고통지수의 합을 구할 수 있습니다.
  • 각 메뉴들이 최댓값이 되는 경우의 수와 최솟값이 되는 경우의 수를 구하기 위해 오름차순으로 스코빌 지수를 정렬합니다.
  • 각 메뉴들이 최댓값이 되는 경우
    • 가장 스코빌 지수가 낮은 메뉴가 최댓값이 되는 경우의 수는 해당 메뉴만을 선택했을 때 한 경우 밖에 없기 때문에 1이 됩니다.
    • 이후부터는 현재 메뉴가 idx번째 메뉴라면, $2^{idx - 1}$번만큼 최댓값이 됩니다.
  • 각 메뉴들이 최솟값이 되는 경우
    • 가장 스코빌 지수가 높은 메뉴가 최솟값이 되는 경우의 수는 해당 메뉴만을 선택했을 때 한 경우 밖에 없기 때문에 1이 됩니다.
    • 그 전으로는 현재 메뉴가 idx번째 메뉴라면, $2^{idx + 1}$번만큼 최솟값이 됩니다.
    • 이를 다르게 표현한다면 $2^{(N - 1) - idx}$가 됩니다.
  • 위와 같이 각 메뉴들이 최댓값, 최솟값이 되는 경우의 수를 구하고 이를 이용하여 주헌고통지수의 합을 구합니다.