문제

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

주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.

'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.

최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다. 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.

이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.

입력
첫 줄에 메뉴의 총 개수 N이 주어진다. 두 번째 줄에는 N개의 메뉴의 스코빌 지수가 주어진다. 모든 스코빌 지수는 0보다 크거나 같고 $2^{31}-1$보다 작거나 같은 정수이다.

출력
한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.

Small (50점)
1 ≤ N ≤ 3,000
Large (200점)
1 ≤ N ≤ 300,000

예제 입력 1
3
5 2 8
예제 출력 1
18

예제 입력 2
6
1 4 5 5 6 10
예제 출력 2
307

접근

아무리 머리를 굴려도 $O(N^2)$ 로직밖에 안 떠올라서 풀이를 조금 참고했다...
일단 정렬은 당연히 해야 한다.

6
1 4 5 5 6 10

위 입력에서 가장 낮은 스코빌 지수가 1이고, 가장 높은 스코빌 지수가 6인 메뉴 조합은 모두 몇 가지일까?
1과 6 사이에 메뉴가 3개 존재하고 각 메뉴를 선택하거나 선택하지 않을 수 있기 때문에 $2^3$, 총 8가지가 나오게 된다.
이런 식으로 중복 순열 논리를 이용해 동일한 주헌고통지수를 갖는 메뉴 조합의 가짓수를 알 수 있다.

---

여기까진 그럴 수 있는데, 모든 최소-최대 조합을 순회하면 $O(N^2)$이기 때문에 시간 초과가 난다.
생각을 조금 바꿔서, 각 원소 arr[i]가 모든 주헌고통지수의 합에 어떻게 기여하는지 생각해보자.

• arr[i]가 어떤 메뉴 조합에 최대로 쓰였다면,
  arr[0]에서 arr[i - 1] 사이에서 하나 이상의 메뉴를 골랐을 것이다.
  따라서 arr[i]가 최대로 쓰이는 횟수는 $2^i-1$번이다. (메뉴를 하나도 안 고르는 경우 한 가지를 빼줬다.)
• arr[i]가 어떤 메뉴 조합에 최소로 쓰였다면,
  arr[i + 1]에서 arr[N - 1] 사이에서 하나 이상의 메뉴를 골랐을 것이다.
  따라서 arr[i]가 최대로 쓰이는 횟수는 $2^{N - 1 - i} - 1$번이다. (역시나 메뉴를 하나도 안 고르는 경우 한 가지를 빼줬다.)

주헌고통지수의 합은Σ (최대 스코빌 지수 - 최소 스코빌지수)이므로 arr[i]가 어떤 메뉴 조합에 최대로 쓰인 횟수만큼은 더하고, 최소로 쓰인 횟수만큼은 빼줘야 할 것이다.
따라서 전체 합은

$\Sigma \,arr[i] * (2^i - 1) - arr[i] * (2^{N-1-i} - 1)$

$=\Sigma \,arr[i] * (2^i - 1 - 2^{N-1-i} + 1)$
$=\Sigma \,arr[i] * (2^i - 2^{N-1-i})$
가 된다.

그리고 이 문제에서 Math.pow()를 쓰면 double 반올림 오차로 틀리게 된다. 그래서 2의 거듭제곱 값은 다음과 같이 누적 곱을 이용해 미리 모두 구해서 배열에 저장해둔 뒤 사용하면 된다.

pow2[0] = 1;
for (int i = 1; i < N; i++) {
    pow2[i] = (pow2[i - 1] * 2) % MOD;
}

이런 수학 문제는 알면 정말 아름답게 풀리는데 모르면 영원히 풀 수가 없다.
이걸 머리에서 떠올려야 한다기보다 그냥 알고 쓰는 게 맞는 거 같다.

구현

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

class Main {
   public static void main(String[] args) throws IOException {
       final long MOD = 1000000007;
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int N = Integer.parseInt(br.readLine());
       StringTokenizer st = new StringTokenizer(br.readLine());
       int[] arr = new int[N];
       long[] pow2 = new long[N];
       pow2[0] = 1;
       
       for (int i = 0; i < N; i++) {
           arr[i] = Integer.parseInt(st.nextToken());
           if (i > 0) {
               pow2[i] = (pow2[i - 1] * 2) % MOD;
           }
       }

       Arrays.sort(arr);
       long answer = 0;
       for (int i = 0; i < N; i++) {
           answer = (answer + arr[i] * (pow2[i] - pow2[N - 1 - i])) % MOD;
       }

       System.out.println(answer);
   }
}