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

www.acmicpc.net/problem/15824

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

---

김유정의 <동백꽃>에서 점순이의, "너 봄감자가 맛있단다."라는 말에서 따온 문제입니다.

---

 

우선 이 문제에서 주어진 예제를 생각해보겠습니다. (예제 입력 1)

 

$\left [ 5,2,8 \right ]$ 와 같이 메뉴의 스코빌 지수가 주어졌을 때 모든 조합의 주헌고통지수의 합을 구해봅시다.

 

그런데 예를 들어 $\left [ 2,8 \right ]$ 의 스코빌 지수를 가진 음식을 먹을 때, 주헌고통지수가 6임은 알기 쉬우나

 

$\left [ 5 \right ]$ 과 같이 스코빌 지수를 가진 음식을 먹을 때 주헌고통지수는 어떻게 계산될 까요?

 

이 경우 스코빌 지수의 최솟값이 5인데 최댓값도 5이므로 주헌고통지수는 0이 될 것입니다. (!)

 

이렇게 조합 하나하나의 주헌고통지수를 통해 그 총합을 구하려면,

 

스코빌 지수 $N$개가 주어졌을 때 가능한 조합의 수가 $2^{N}-1$개 이므로 복잡도가 $O\left( 2^{N} \right)$이 될 것입니다.

---

 

이제 좀 더 자세히 관찰해보겠습니다.

 

$\left [ 5,2,8 \right ]$ 에서 가능한 조합은 다음과 같습니다.

 

$\left [ 5,2,8 \right ]$

$\left [ 5,2 \right ]$

$\left [ 2,8 \right ]$

$\left [ 5,8 \right ]$

$\left [ 5 \right ]$

$\left [ 2 \right ]$

$\left [ 8 \right ]$

 

따라서, 위에서부터 순서대로 $\left ( 6 \right )+\left ( 3 \right )+\left ( 6 \right )+\left ( 3 \right )+\left ( 0 \right )+\left ( 0 \right )+\left ( 0 \right )=18$이 됨을 알 수 있습니다. (예제 출력 1)

 

그런데 이때 식을 쪼개어, "빼야 하는 최솟값"과 "더해야 하는 최댓값"을 분리해보겠습니다.

 

그러면 다음과 같은 결과가 나옵니다.

 

 $\left ( -2-2-2-2-5-5-8 \right )+ \left ( 8+8+8+8+5+5+2 \right )=18$

 

즉, 모든 조합 중에서 2가 최솟값인 조합이 4개, 5가 최솟값인 조합이 2개, 8이 최솟값인 조합이 1개였다는 뜻입니다.

 

이는 꽤나 의미심장합니다.

---

 

$\left [ 5,2,8 \right ]$을 오름차순으로 정렬한 $\left [ 2,5,8 \right ]$을 생각해보겠습니다.

 

잘 관찰해보면 2가 최솟값인 조합은 "5가 포함되어 있느냐/아니냐", 그리고 "8이 포함되어 있느냐/아니냐"로 구분할 수 있습니다.

 

따라서 2가 최솟값인 조합의 수는 $2\times 2=4$개가 됩니다.

 

같은 논리로 5가 최솟값인 조합과 8이 최솟값인 조합의 개수가 각각 2, 1이 됨을 알 수 있습니다.

 

이를 일반화하여 오름차순으로 정렬된 $N$개의 스코빌 지수 $\left[ X_{1},X_{2},\cdots,X_{N} \right]$을 생각해보겠습니다.

 

$X_{1}$에 대해 같은 생각을 해보면, $X_{1}$이 최솟값인 조합의 개수는 $2^{N-1}$ 임을 알 수 있습니다.

 

$X_{2}$에 대해 같은 생각을 하면 $X_{2}$가 최솟값인 조합의 개수는 $2^{N-2}$ 이고,

 

결과적으로 $X_{i}$가 최솟값인 조합의 개수는 $2^{N-i}$가 될 것입니다. ($1\leq i\leq N$)

 

이제 $X_{i}$가 최댓값인 조합의 개수도 쉽게 알 수 있습니다. 바로 $2^{i-1}$입니다. ($1\leq i\leq N$)

---

이제 다시 이 식으로 돌아오겠습니다.

 

$\left ( -2-2-2-2-5-5-8 \right )+ \left ( 8+8+8+8+5+5+2 \right )=18$

 

이 식을 2끼리, 5끼리, 8끼리 묶어서 다음과 같이 나타낼 수 있습니다.

 

$2\times \left ( 1-4 \right )+5\times \left ( 2-2 \right )+8\times \left ( 4-1 \right )$

 

방금 전에 했던 일반화를 떠올려보면 주헌고통지수의 합을 이제 쉽게 알 수 있겠습니다.

 

오름차순으로 정렬된 $\left [ X_{1},X_{2},\cdots,X_{N} \right ]$에 대해서 주헌고통지수의 합은 다음과 같이 나타낼 수 있습니다.

 

$X_{1}\times \left ( 2^{0}-2^{N-1} \right )+X_{2}\times \left ( 2^{1}-2^{N-2} \right )+\cdots+X_{N}\times \left ( 2^{N-1}-2^{0} \right )$

 

즉 $2^{0},2^{1},2^{2},\cdots,2^{N}$의 modulo $\left ( 10^{9}+7 \right )$ 값을 미리 구할 수 있다면

 

주헌고통지수의 합도 $O\left ( N \right )$ 정도에 구할 수 있다는 뜻입니다.

 

따라서 $2^{0}$ 부터 $2^{N-1}$ 까지의 modulo $\left ( 10^{9}+7 \right )$ 값을 $O\left ( N \right )$에 전처리해주면

 

시간제한을 초과하지 않고 답을 구할 수 있습니다.

---

 

사실 여기엔 함정이 하나 있는데, 스코빌 지수 $N$개가 정렬된 상태로 주어진다는 보장이 없다는 것입니다.

 

따라서 스코빌 지수 $N$개를 오름차순(또는 내림차순)으로 정렬해야 하는데,

 

이때 정렬을 $O\left ( N^{2} \right )$에 하면 Small정도만 통과하게 될 것입니다.

 

따라서 $O\left ( NlogN \right )$에 정렬을 수행하면 코드의 전체 시간복잡도는 $O\left ( NlogN \right )$이 됩니다.

 

저는 stdlib.h 헤더파일에 내장된 qsort함수를 사용하여 정렬을 했습니다.

 

또한 음수 모듈러 연산에 대해서도 주의를 해줘야 합니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007

int compare (const void* m, const void* n);

int main() {
	int N;
	scanf("%d", &N);
	
	long long* scoville_array = (long long*)malloc(sizeof(long long) * N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &scoville_array[i]);
	}
	qsort(scoville_array, N, sizeof(long long), compare);

	long long* power_array = (long long*)malloc(sizeof(long long) * N);
	power_array[0] = 1;
	for (int i = 1; i < N; i++) {
		power_array[i] = (2 * power_array[i-1]) % mod;
	}
	
	long long answer = 0;
	for (int i = 0; i < N; i++) {
		
		long long temp = (scoville_array[i] % mod) * ((power_array[i] - power_array[N - 1 - i] + mod) % mod);
		
		answer = (answer + (temp % mod)) % mod;
	}
	printf("%lld", answer);
	
	free(scoville_array);
	free(power_array);
	return 0;
}

int compare (const void* m, const void* n) {
	return *(int*)m - *(int*)n;
}

 

(C11, Small에서는 1116KB, 0ms, Large에서는 5804KB, 108ms. 제출번호 26308270)

---

C11의 qsort 내장함수는 최악의 경우 $O\left ( N^{2} \right )$인 것으로 알고 있습니다.

 

이 문제의 경우 그걸 찌르는 데이터가 없어서 그런지 잘 통과된 듯한 모습입니다.

 

만약 내장된 qsort로 해결할 수 없는 문제였다면, 랜덤하게 피벗을 뽑는 퀵소트를 직접 구현하거나,

 

C++ STL(및 기타 언어)에 내장된 sort함수를 사용하거나, 병합 정렬 정도를 직접 구현하면 해결될 것 같습니다.