BOJ 15824 너 봄에는 캡사이신이 맛있단다

너 봄에는 캡사이신이 맛있단다
(http://boj.kr/15824)

이 문제는 수학문제에 가까운 것 같다. 우선 최솟값과 최댓값만 정하면 중간에 뭐가 들어가던 상관이 없다는 아이디어를 떠올려야 한다.
즉, 정렬한 뒤에 양쪽에 두 원소를 고른 뒤 사이에 있는 원소는 들어가던 말던 주헌고통지수는 달라지지 않는다.

우선 그냥 식을 세워봤다. \(A_i\)는 \(i\)번째로 스코빌지수가 작은 메뉴다.
\(2^{n-2}(A_n-A_1)+2^{n-3}(A_{n-1}-A_1)+\cdots+2^{0}(A_2-A_1)\)
\(+2^{n-3}(A_n-A_2)+2^{n-4}(A_{n-1}-A_2)+\cdots+2^{0}(A_3-A_2)\)
\(+\cdots\)
\(+2^0(A_n-A_{n-1})\)

각 행에서 계속 빼는 메뉴를 기준으로 묶으면,
\(2^{n-2}A_n+2^{n-3}A_{n-1}+\cdots+2^0A_2-(2^{n-1}-1)A_1\)
\(+2^{n-3}A_n+2^{n-4}A_{n-1}+\cdots+2^0A_3-(2^{n-2}-1)A_2\)
\(+\cdots\)
\(+2^0A_n-(2^1-1)A_{n-1}\)
이 된다. (\(2^n+2^{n-1}+\cdots+2^0=2^{n+1}-1\)이다.)

앞에 더하는 것도 열끼리 묶을 수 있다. 모두 정리하면,
\((2^{n-1}-1)A_n+(2^{n-2}-1)A_{n-1}+\cdots+(2^1-1)A_2-(2^{n-1}-1)A_1-(2^{n-2}-1)A_2-\cdots-(2^1-1)A_{n-1}\)
이다.

결론은 그냥 식을 정리하면 된다.

#include <bits/stdc++.h>
 
const long long r = 1e9 + 7;
 
long long arr[300000];
 
int main() {
  int n;
  long long ans = 0, t;
 
  scanf("%d", &n);
 
  for (int i = 0;i < n;++i)
    scanf("%lld", &arr[i]);
 
  std::sort(arr, arr + n);
 
  t = 2;
  for (int i = 1;i < n;++i) {
    ans = (ans + arr[i] % r * (t - 1 + r) % r) % r;
    t = t * 2 % r;
  }
  t = 2;
  for (int i = n - 2;i >= 0;--i) {
    ans = (ans - arr[i] % r * (t - 1 + r) % r + r) % r;
    t = t * 2 % r;
  }
 
  printf("%lld", ans);
 
  return 0;
}