백준 15824번: 너 봄에는 캡사이신이 맛있단다 (C++)

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

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

---

Solved By: Combinatorics, Exponention By Squaring

 

주어진 수열로부터 모든 조합을 찾아서 해당 조합의 최댓값 - 최솟값을 구하는 문제였습니다.

하지만, 모든 조합을 찾는 데에는 시간 초과가 발생합니다.

구글링으로 솔루션을 찾았는데 정말 배워둘 만한 테크닉인 거 같습니다.

 

어떤 값 v가 존재한다고 하겠습니다. v가 어떤 조합에서든 최댓값이 될 경우는 정렬을 시켰을 때, v를 포함한 v 이전의 값들을 가지고서 조합을 만듭니다. v 이전의 값들이 a, b, c가 존재한다면 a가 존재하는지 존재하지 않는지에 대한 경우의 수 2가지, b 또한 2가지, c 또한 2가지로 총 2^3개의 조합이 나옵니다. 그리고 v가 최솟값이 될 경우는 그 반대의 경우를 생각하면 됩니다.

 

그렇게 하여 모든 수열들에게 적용하면 수열에서 나올 수 있는 조합에서 최댓값들과 최솟값을 구할 수 있습니다. 어떤 한 조합에서의 최댓값, 최솟값 1:1 매칭이 아닌 모든 조합의 최댓값들과 모든 조합의 최솟값들의 N:N 매칭으로 차를 구하여 답을 내놓을 수 있습니다.

 

즉, 이번 문제에서의 관점은 자칫 잘못하면 모든 조합을 구하여 그 안에서 최댓값들과 최솟값들을 구하게 하는 트릭이었습니다. 관점을 조합이 아닌 '어떤 값이 최댓값이 되는 경우'를 생각한다면 풀리는 문제였습니다.

 

다시 한 번, 관점의 차이와 새로운 테크닉을 배우는 문제였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define ll long long
using namespace std;

int n;
vector<int> v;

ll POW(int a, int b){
    if(b == 0) return 1;
    if(b == 1) return a;
    
    ll value = POW(a, b / 2);
    
    if(b % 2 == 0){
        return (value * value) % MOD;
    }
    else{
        return (value * value * a) % MOD;
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        int value; cin >> value; v.push_back(value);
    }
    
    sort(v.begin(), v.end());
    
    ll result = 0;
    for(int i = 0; i < v.size(); i++){
        result += v[i] * (POW(2, i) - POW(2, v.size() - i - 1) + MOD) % MOD;
        result %= MOD;
    }
    
    cout << result;
}