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

 

 조합론과 분할 정복 기반 거듭제곱을 응용한 문제다. Large 케이스에서 N이 최대 300,000까지 들어올 수 있고, 모든 조합을 하나하나 고려한다면 지수시간에 해당하는 시간 복잡도를 가지기 때문에 브루트 포스는 사용할 수 없다.

 하지만, 문제를 잘 생각해 보면 알 수 있듯이 주헌고통지수라는 것은 특정 조합에서의 최댓값과 최솟값만 있어도 구해낼 수 있다. 그리고 모든 메뉴를 스코빌 지수 기준으로 정렬해 둔다면, 어떤 메뉴가 최댓값이 되는 경우와 최솟값이 되는 경우를 바로 구해낼 수 있다. 

 

 만약 예제 2번의 경우에서, 6이 최댓값이 되는 경우를 생각하면 위처럼 생각할 수 있다. 6은 조합에 포함되어야 하고, 10은 포함되어서는 안 된다. 그리고 나머지 더 작은 수들에 대해서는 조합 내 포함여부가 6이 최댓값이 되는 데에 영향을 주지 않는다. 하지만 저렇게 구해내게 되면 6만 원소로 포함된 조합의 경우도 포함된다. 하지만 문제 내용에 의해서 다른 음식이 존재해야만 주헌고통지수를 구해낼 수 있으므로, -1을 해주어 그 예외 경우를 빼준다.

 최솟값은 당연히 이를 반대로 생각해서 구하면 된다. 결국 필요한 것은 메뉴 리스트의 정렬 이후, 각 인덱스별 값이 최댓값과 최솟값이 되는 경우를 2의 거듭제곱을 통해 구하고 그 둘의 차이만큼 값에 곱해 결과에 더해주면 된다(최댓값이 되는 경우에는 주헌고통지수의 합에 더해졌을 것이고, 최솟값이 되는 경우에는 주헌고통지수의 합에서 빼졌을 것이다).

 

단, 여기서 거듭제곱 구하는 과정을 브루트 포스로 하게 되면, N 값이 커졌을 때 시간 초과가 날 것이다. 따라서 분할 정복을 통해 거듭제곱을 구하는 테크닉을 사용해 시간 복잡도를 줄여 문제를 해결할 수 있다.

#include <iostream>
#include <algorithm>
#define MOD 1000000007

using namespace std;

long long menuList[300000];

long long bigPow(long long base, long long exp) {
    if(exp==0) return 1;
    if(exp==1) return base;

    long long half = bigPow(base, exp/2);
    if(exp%2==0) {
        return half*half%MOD;
    } else {
        return half*half%MOD*base%MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for(int i=0; i<n; i++) {
        cin >> menuList[i];
    }

    sort(menuList, menuList+n);

    long long result = 0;

    for(int i=0; i<n; i++) {
        long long maxCnt = bigPow(2, i)-1;
        long long minCnt = bigPow(2, n-i-1)-1;
        
        result += menuList[i]*(maxCnt-minCnt);
        result %= MOD;
    }

    cout << result;
}