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

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

 

처음 아이디어는 nCr마냥 각 조합별 최솟값, 최댓값을 구하고, 해당 최솟값 최댓값의 차를 그 조합수 만큼 곱하여 주헌고통지수 합을 구했었는데 3중 for문과, nCr 조합 수를 for문으로 구하는 그 시간 때문에 시간 초과 문제가 있었다.

 

그래서 알아보다가 밑의 블로그 글의 힌트를 참고했다.

https://cding.tistory.com/119

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

 

즉, 정렬된 리스트를 for문으로 순환하면서 최솟값 A[idx], 최댓값 A[N-1 - idx]는 각각 $2^{N-1}-1$번씩 곱하고 각각 빼고 더하면 된다는 것이다.

 

저번 1629번 문제에서, 큰 수를 다룰 때 미리 나눔으로써 시간 초과 문제를 다뤘었는데, 이번에도 최솟값의 합, 최댓값의 합을 미리 나눠야 하는 1000000007로 나누었다.

 

2의 거듭제곱 또한 미리 계산하고 1000000007로 나누어주었다.

 

# https://www.acmicpc.net/problem/15824
# 수학, 조합론

import sys

N = int(input())
scovs = list(map(int, sys.stdin.readline().split()))
scovs.sort()

div = 1000000007

square2 = [0 for _ in range(N)]
temp = 1
for idx in range(N) :
    square2[idx] = temp - 1
    temp *= 2
    temp %= div

minimums = 0
maximums = 0
for idx in range(N) :
    minimums += square2[N-1 - idx] * scovs[idx]
    maximums += square2[N-1 - idx] * scovs[N-1 - idx]
    minimums %= div
    maximums %= div

print((maximums%div - minimums%div)%div)