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

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

 

처음에는 DP로 생각했으나 O(N^2) 에서 시간을 더 줄이는 것이 불가능했다.

 

이 문제는 모든 조합을 구하는 것은 O(2^N - 1) 로 불가능하다.

 

가장 중요한 추론은 어떠한 조합이든 결국 최댓값과 최솟값만 알면 스코빌지수를 알 수 있는 것이다.

 

1, 2, 3, 4 가 있을 때

1 ,2, 4

1, 3, 4

1, 4

 

스코빌지수는 모두 3이다. 

 

두번째 떠올려야할 아이디어는 위처럼 꼭 모든 조합을 해봐야알 필요는 없다. 사실 이것을 생각해내기가 가장 어려운 것 같다. 당연히 조합을 먼저 구하려고 하는 것이 일반적이기 때문이다.

 

1, 2, 3이 있다고 하자.

3은 최댓값으로 (1, 3), (2, 3), (1, 2, 3) 으로 총 3번의 최댓값이 될 수 있다. 

2는 최댓값으로 (1, 2) 총 1번 될 수 있으며 (2,3) 에서 총 1번 최솟값이 될 수 있다.

1은 최댓값은 될 수 없고 최솟값으로 (1, 2) (1, 3) (1, 2, 3) 총 3번의 최솟값이 될 수 있다.

 

그러므로, 

i번째 수는 

2^(i - 1) - 1 번 최댓값이 될 수 있고

2^(N - i - 1) - 1 번 최솟값이 될 수 있음을 알 수 있다. 

 

그리고 편의를 위해 각 자릿수의 2^N - 1 을 미리 구해놓도록 하자.

powArr[i] = 2^i - 1이다.

 

그리고 위를 코드로 표현하면

for(int i = 0; i < N; i++){
        ans += powArr[i] * arr[i] % 1'000'000'007;
        ans -= powArr[N - 1 - i] * arr[i] % 1'000'000'007;
        ans %= 1'000'000'007;
    }

 

모듈러 연산은 문제의 조건때문에 진행했다.

 

조합을 일일이 구하지 않고 문제가 원하는 것을 찾는 아이디어가 중요한 문제였다. 코테스타일은 아니지만 충분히 좋은 문제.

 

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


int main(){
    int N; cin >> N;
    long long powArr[300001];
    long long arr[300001];

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

    int p = 1;
    for(int i = 0; i < N; i++){
        if(i == 0){
            powArr[i] = 0;
            p *= 2;
        }
        else{
            powArr[i] = p - 1;
            // powArr[i] %= 1'000'000'007;
            p *= 2;
            p %= 1'000'000'007;
        }
    }

    sort(arr, arr + N);
    long long ans = 0;

    for(int i = 0; i < N; i++){
        //cout << powArr[i] << endl;
        ans += powArr[i] * arr[i] % 1'000'000'007;
        ans -= powArr[N - 1 - i] * arr[i] % 1'000'000'007;
        ans %= 1'000'000'007;

        //cout << ans << endl;
    }

    cout << (ans + 1'000'000'007) % 1'000'000'007 << '\n';
}