백준/15824번/너 봄에는 캡사이신이 맛있단다/골드2

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

문제 설명

Site: Baekjoon
Number: 15824
Category: Mathematics
Rank: Gold 1

여러 숫자가 주어졌을 때 모든 조합에서 나오는 최댓값 - 최솟값의 합을 구하는 문제입니다.

문제 풀이

모든 조합을 확인한다면 N의 최대치인 30만의 기준으로 약 450억이 되어 시간초과가 발생하게 됩니다.

그러므로 각 숫자 별 조합에 들어가는 최댓값의 경우와 최솟값의 경우를 확인하여 최종 합에 이를 더하는 것으로 구할 수 있습니다.

들어온 숫자를 크기 순으로 정렬하고, i번째 순서의 숫자가 최댓값으로 나오는 조합의 수는 2^i, 최솟값으로 나오는 조합의 수는 N-i-1이 되며

최댓값 횟수에서 최솟값 횟수를 빼고 i번째 숫자를 곱해준 값을 sum에 더하는 과정을 모든 원소에서 진행하면 정답이 도출 됩니다.

여기서 거듭제곱 하는 과정에서 시간초과가 발생할 수 있으므로, 이진수를 활용한 거듭제곱을 활용하여 시간복잡도를 줄였습니다.

#include <iostream>
#include <vector>
#include <algorithm>

long long MOD = 1000000007;

using namespace std;

//이진수를 활용한 거듭제곱
long long binarypow(long long base, long long exp)
{
	long long ret = 1;

	while (exp > 0)
	{
		if (exp & 1)
			ret = (ret * base) % MOD;

		base = (base*base) % MOD;
		exp = exp >> 1;
	}

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	vector<long long> v;

	int N;
	cin >> N;

	long long sum = 0;

	for (int i = 0; i < N; i++)
	{
		long long num;
		cin >> num;
		v.emplace_back(num);
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < N; i++)
	{
    //최댓값으로 나오는 횟수
		long long maxcnt = binarypow(2, i);

    //최솟값으로 나오는 횟수
		long long mincnt = binarypow(2, N - i - 1);

		sum = (sum + (maxcnt * v[i] % MOD - mincnt * v[i] % MOD + MOD) % MOD) % MOD;

	}

	cout << sum;

	return 0;
}