백준 15824번 너 봄에는 캡사이신이 맛있단다 - 스위프트(Swift) 풀이

 서브 태스크 문제로 small N과 large N 각각 점수가 매겨져 있어 small N만 통과해도 부분점수를 받을 수 있다.

 먼저 small N에 맞게 풀이를 떠올리는 것은 쉽다. 결국 최소와 최대만 필요하므로 2개를 뽑아 그 2개가 (최소, 최대)가 되는 경우의 수를 각각 세서 곱해주면 된다. 이때 정렬을 하면 경우의 수를 쉽게 구할 수 있다. [1, 3, 4, 10, 11]이 있고 (3, 11)이 각각 최소, 최대가 되는 경우의 수를 구해보자. 3보다 크고 11보다 작은 숫자는 [4, 10]이 있으므로 이것들이 각각 있는 경우와 없는 경우를 고려하면 2^2가지이다. 모든 경우의 수를 나열하면 [3, 11], [3, 4, 11], [3, 10, 11], [3, 4, 10, 11]이 되겠다. 이렇게 풀이할 경우 (최소, 최대) 쌍을 고르는데 O(n^2)이 되기 때문에 300,000인 large N은 통과할 수가 없다.

 조금만 더 생각해보면 굳이 최소와 최대를 항상 같이 고려할 필요는 없음을 알 수 있다. 어차피 최대와 최소의 차를 계산하는 것이므로 최대가 되는 경우에는 +를 하고 최소가 되는 경우에는 -를 해주면 되기 때문에 최소와 최대를 각각 구해도 된다. 다시 [1, 3, 4, 10, 11]인 상황으로 돌아가 보자. 4가 최대가 되는 경우의 수는, 4보다 작은 애들 [1, 3]이 각각 있거나 없을 수 있으므로 2^2가 된다. 또 4가 최소가 되는 경우의 수는, 4보다 큰 애들 [10, 11]이 있거나 없을 수 있으므로 2^2가 된다. 이것을 i번째 원소에 대해 일반화하면, arr[i]가 최대가 되는 경우의 수는 2^i가지, 최소가 되는 경우의 수는 2^(N-1-i) 가지로 arr[i]*2^i - arr[i]*2^(N-1-i)이다. 이제 mod 연산만 잘 해주면 된다.