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

매운 거 먹기 좋은 날씨인데.. 나는 뭐 하냐..

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

---

뭔가 어려워 보이는 문제이다. 음식의 모든 조합을 먹어 보라고 했으니 $2^{N}$개의 조합을 모두 따져 볼까?

$O(2^{N})$ 풀이

음식점의 모든 조합을 구하고, 모든 조합의 주헌고통지수를 더한다.

 

1초만에 떠올릴 수 있는 풀이지만, 당연히 맞을 리가 없다. Small 태스크만 봐도 $N=3000$이다. 아무래도 조금 더 생각해봐야 할 것 같다.

$O(N^{2})$ 풀이

위에서 말했듯이, 이 음식점의 모든 음식 조합은 $2^{N}$개이다. 상식적으로 $2^{N}$개를 일일이 다 따져볼 수가 없으니, 기본적으로 여러 조합을 한 번에 처리한다는 마인드로 접근해야 한다.

 

일단 스코빌 지수 $S$를 오름차순으로 정렬하자. 이제부터 $S_{i}$는 $i$번째로 큰 스코빌 지수를 의미한다.

 

$S$가 정렬되었으므로 $i < j$일 때 $S_i \le S_j$이다. 음식 조합 중 $S_i$와 $S_j$를 각각 최솟값과 최댓값으로 갖는 조합은 $2^{j-i-1}$개이다. $[i, j]$ 구간에서 $i$번과 $j$번 원소를 무조건 포함하고, 나머지 $j-i-1$개의 원소는 각각 선택하거나 선택하지 않을 수 있기 때문이다. 이 조합의 주헌고통지수는 $S_j - S_i$이므로, 구하는 정답은 다음과 같다.

 

$\sum_{i~<~j}{(S_j-S_i)~2^{j-i-1}}$

 

하지만 이 풀이로는 Large 태스크를 통과할 수 없다. $N <= 300,000$이기 때문이다. $O(NlogN)$ 이하의 풀이를 생각해야 한다.

$O(N)$ 풀이

놀랍게도 이 문제를 선형 시간에 해결할 수 있다. 사실 이 문제처럼 원소를 가지고 뭔가 계산하는 문제는 손으로 직접 써 봐야 한다.

스포일러가 있다

위에서 제시한 정답 식을 풀어서 써 보자. $i$번째 줄의 최댓값이 $S_i$이 되도록 정리해 보았다.

 

$\sum_{i~<~j}{(S_j-S_i) \times 2^{j-i-1}}$

$=(S_2-S_1)\times2^{0}+$

$(S_3-S_2) \times 2^0 + (S_3-S_1) \times 2^1~+$

$(S_4-S_3) \times 2^0 + (S_4-S_2) \times 2^1 + (S_4 - S_1) \times 2^2 ~+$

$(S_5-S_4) \times 2^0 + (S_5-S_3) \times 2^1 + (S_5-S_2) \times 2^2 + (S_5-S_1) \times 2^3~+$

$~~~~\vdots$

$=(S_n-S_1) \times 2^0 + ((S_n+S_{n-1})-(S_2+S_1)) \times 2^1 + ((S_n+S_{n-1}+S_{n-2})-(S_{3}+S_2+S_1)) \times 2^2 + \cdots$

 

규칙성이 보이는가? 위의 수열에서 $i~(i=1,2,3,\cdots)$번째 항을 $a_i$라 하면, $a_i$는 뒤쪽 $i$개의 합에서 앞쪽 $i$개의 합을 빼고, 거기에 $2^{i-1}$을 곱한 값이다. 가장 큰 원소 $i$개의 합을 $max_i$, 가장 작은 원소 $i$개의 합을 $min_i$라고 하면 구하는 정답은 다음과 같다.

 

$\sum_{i=1}^{n}{(max_i - min_i) \times 2^{i-1}}$

 

$max_i$와 $min_i$는 prefix sum을 구현하여 상수 시간에 계산할 수 있다. 따라서 정답을 $O(N)$ 시간에 구할 수 있다.

---

경우의 수가 너무 많을 때에는 한번에 여러 개의 경우를 처리할 수 있는 방법을 찾아야 한다.