[백준] 15824 너 봄에는 캡사이신이 맛있단다

문제 링크

http://icpc.me/15824

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

풀이

수학 문제다.

각 수가 최댓값, 최솟값이 될 수 있는 경우의 수를 각각 잘 계산하면 된다.

정렬된 배열 arr에서 arr[i]가 최댓값이 될 수 있는 경우의 수는 arr[0]~arr[i-1]의 모든 조합의 수인 2^i 같고, arr[i]가 최솟값이 될 경우의 수는 

arr[i+1]~arr[n-1]까지의 모든 조합의 수인 2^(n-i-1)이다.

cf) 2^n을 미리 구해 놓을때 mod를 하지 않으면 시간 초과를 받을 수 있다.

파이썬에서 큰수 연산 곱하기의 시간복잡도가 O(n^1.585)라고 한다.

참고 자료: https://stackoverflow.com/questions/31139591/measuring-big-o-of-multiplication-in-python#:~:text=Python%20uses%20the%20Karatsuba%20multiplication,O(n%5E2).

코드

n = int(input())
arr = sorted(list(map(int, input().split())))
ans = 0
mod = int(1e9 + 7)
pw = [1]

for i in range(n):
    pw.append(pw[-1] * 2)

for i in range(n):
    ans += (pw[i] * arr[i] - pw[n - i - 1] * arr[i])

ans %= int(1e9 + 7)
print(ans)