모든 조합에서 최솟값, 최댓값을 구하여 그 차이만큼 더하는 문제입니다.
n이 300000만이라 모든 조합을 다 구한 뒤 최소, 최대를 구할 수는 없습니다.
그래서 시간 복잡도를 O(n)이나 O(nlgn)의 문제 풀이를 생각하다가 정렬을 먼저 하게 되면 최소, 최대를 쉽게 구할 수 있으니
정렬을 하고 처음에는 시작점, 끝점을 잡아서 그 사이에 가능한 경우의 수를 보려고 했는데
그래도 시간 복잡도가 O(n^2) 이어서 고민하다가 굳이 시작점, 끝점을 잡을 필요가 없다는 것을 알게 되었습니다.
어차피 최댓값을 더하고 최솟값을 빼면 되니 입력 배열 arr을 정렬을 한 뒤
i라는 기준을 잡고 i가 최댓값일 때 경우의 수는 더해주고 최솟값일 때 경우의 수는 빼주면 됩니다.
i가 최댓값일 경우는 1~i-1의 스코빌 지수는 정렬을 했으니 무조건 작거나 같기 때문에
1~i-1의 각각 인덱스가 포함될지 제외될지를 정하면 2^(i-1)이라는 경우의 수를 얻을 수 있습니다.
i가 최솟값일 경우는 i+1~n의 스코빌 지수는 무조건 크거나 같기 때문에 앞에처럼 구하면 2^(n-i)이라는 경우의 수를 얻을 수 있습니다.
최댓값 * 최댓값일 때 경우의 수 - 최솟값 * 최솟값일 때 경우의 수 = 2^(i-1) * arr[i] - 2^(n-i) * arr[i] = (2^(i-1) - 2^(n-i)) * arr[i]입니다.
모든 경우의 수를 봐야 하니 1~n까지 위처럼 하시면 됩니다.
모듈러 연산을 잘 처리하시길… ㅠ 모듈러 연산 싫어요…
시간 복잡도는 정렬을 해서 O(nlgn)입니다.
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod ((int)1e9 + 7)
int pow_2[300005], arr[300005], n, ans;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
sort(arr + 1, arr + n + 1);
pow_2[0] = 1;
for (int i = 1; i <= 300000; i++)
pow_2[i] = 1LL * pow_2[i - 1] * 2 % mod;
for (int i = 1; i <= n; i++)
ans = (ans + (pow_2[i - 1] - pow_2[n - i] + mod) % mod * 1LL * arr[i]) % mod;
cout << ans << '\n';
return 0;
}