[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다

 

[백준 15824번 C/C++] 너 봄에는 캡사이신이 맛있단다

 

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

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

---

 

해결전략

 

수학
정렬
조합론
분할 정복을 이용한 거듭제곱

 

 

---

 

정답코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n; // 메뉴의 총 개수
vector<long long> v;
vector<long long> two;

const int MOD = 1000000007;

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

	cin >> n;
	v.resize(n);
	two.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	long long temp = 1;
	for (int i = 0; i < n; i++) {
		two[i] = temp - 1;
		temp *= 2;
		temp %= MOD;
	}

	long long maxSco = 0;
	long long minSco = 0;
	for (int i = 0; i < n; i++) {
		minSco += ((two[n-1-i] - 1) * v[i]) % MOD;
		maxSco += ((two[i] - 1) * v[i]) % MOD;
	}

	cout << (maxSco % MOD - minSco % MOD + MOD) % MOD << "\n";

	return 0;
}

 

 

---