[백준] 15824 - 너 봄에는 캡사이신이 맛있단다 힌트, 풀이 및 코드(C++)

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

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

 

1. 문제

- 첫 줄에 메뉴의 종류 $N$이 주어짐.

- 두 번째 줄에 각 메뉴의 스코빌 지수가 주어짐.

- 가능한 모든 2 가지 이상의 메뉴 조합들에서, (가장 높은 스코빌 지수) - (가장 낮은 스코빌 지수)의 합을 구하여라.

 

2. 힌트

 

힌트 1

모든 조합에 대해 최저, 최대 스코빌 지수를 구하는 방식으로는 시간복잡도가 너무 높아 문제를 시간 안에 해결할 수 없다.

중요한 포인트는, 모든 조합을 다 구할 필요가 없이 각 조합에서 최대, 최소 값만 알면 우리가 구하고자 하는 값을 구할 수 있다는 것이다.

 

힌트 2

어떤 메뉴 $X$가 포함되는 조합의 개수는 총 $2^{N-1}-1$ 가지이다.

 

힌트 3

가장 높은 스코빌 지수가 더해지는 횟수는 총 $2^{N-1}-1$가지이다.

 

 

3. 문제 관찰 과정 및 풀이

 

가장 처음 할 수 있는 생각은 "모든 조합을 구한 뒤에 (최대, 최소) 쌍을 구해서 더하자" 이다.

물론 이렇게 풀면 시간 초과가 나겠지만, 사실 저 아이디어는 굉장히 중요한 아이디어를 내포하고 있다.

"어차피 어떤 조합을 선택하든, 최대값과 최소값만 알면 된다" 라는 것이다.

 

이 아이디어를 조금만 더 확장해 보자.

많은 문제에서 사용되는, "순서 바꾸기" 테크닉을 사용할 차례이다.

즉, 조합을 선택한 뒤에 최대, 최소값을 구하는 것이 아니라, 먼저 최대, 최소값을 선택한 뒤에 조합들의 개수를 세는 것이다.

(어차피 조합이 어떻든지 최대값과 최소값만 알면 되기 때문에 이런 접근이 가능하다.)

 

가령, 문제의 예제 2인,

6
1 4 5 5 6 10

를 생각해 보자.

 

일단 최대값 먼저 생각하면,

10을 최대값으로 갖는 조합은 총 $2^5-1$가지이므로, 그 모든 $2^5-1$가지의 조합에서는 10을 고통 지수에 더해야 한다.

6을 최대값으로 갖는 조합은 총 $2^4-1$가지이므로, 그 모든 $2^4-1$가지의 조합에서는 6을 고통 지수에 더해야 한다.

...

1을 최대값으로 갖는 조합은 총 $2^0-1 = 0$가지이므로, 1은 어떤 조합에서도 고통 지수에 더해지지 않는다.

 

다음으로 최소값을 생각하면,

1을 최소값으로 갖는 조합은 총 $2^5-1$가지이므로, 그 모든 $2^5-1$가지의 조합에서는 1을 고통 지수에 빼야 한다.

4를 최소값으로 갖는 조합은 총 $2^4-1$가지이므로, 그 모든 $2^4-1$가지의 조합에서는 4를 고통 지수에 빼야 한다.

...

10을 최소값으로 갖는 조합은 총 $2^0-1 = 0$가지이므로, 10은 어떤 조합에서도 고통 지수에 빼지지 않는다.

 

 

이를 일반화 하면, 모든 스코빌지수를 정렬한 값이 $A[1], A[2], \cdots , A[n]$ 이라고 하면, 정답은

$$(2^{N-1}-1)(A[n]-A[1]) + (2^{N-2}-1)(A[n-1]-A[2]) + \cdots + (2^0-1)(A[1]-A[n])$$

으로 계산할 수 있다.

 

구현에서도 몇 가지 포인트가 있는데, $2^x-1$을 $N$번 그냥 계산하게 되면 시간초과가 나므로 $2^x-1$을 미리 저장하는 배열을 하나 만들어 둬야 한다.

또한, C++에서의 음수의 나머지 연산에 유의하며 연산을 진행해야 한다.

 

 

4. 코드

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ll n;
    ll arr[300005];
    ll two[300005];
    ll MOD = 1'000'000'007;
    ll temp = 1;
    ll p=0, m=0;

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

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

    sort(arr, arr+n);

    for (int i=n-1; i>0; i--) {
        p += two[i] * arr[i];
        m += two[i] * arr[n-1-i];
        p%=MOD;
        m%=MOD;
    }
    cout << (p%MOD + MOD - m%MOD) % MOD << '\n';
}

 

 

5. 여담

사실 나머지 연산 잘못해서 무려 10번가량이나 박아버렸다.

나머지 연산 귀찮다고 안보다가 결국에는 피를 보는 일이 생겼다... 대회에서 안이런걸 다행으로 여겨야겠다.

 

위 방식은 $2^x-1$을 메모이제이션 하는 방식을 사용했지만, 분할 정복을 활용하여 제곱을 계산해도 시간 안에 풀 수 있다.