문제

주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.

'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.

최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다. 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.

이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.

입력

첫 줄에 메뉴의 총 개수 N이 주어진다. 두 번째 줄에는 N개의 메뉴의 스코빌 지수가 주어진다. 모든 스코빌 지수는 0보다 크거나 같고 231-1보다 작거나 같은 정수이다.

출력

한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.

풀이

브루트 푸스 풀이와 좀 더 똑똑하게 푸는 방식이 존재한다.

먼저 브루트포스 풀이이다.
최소값을 지정하는 변수 i, 최대값을 지정하는 변수 j를 이용해 2중 for문을 만들어 선택해준다.
이때 존재할 수 있는 조합의 개수는 i-j-1이다.
따라서 조합의 개수와 최댓값과 최소의 차이를 곱해서 계속해서 더해주면 된다.

input = open(0).readline

def faster(n):
    if n in pow_m: return pow_m[n]
    pow_m[n] = pow(2, n, MOD)
    return pow_m[n]
    
pow_m = dict()
N = int(input())
arr = sorted(map(int, input().split()))
MOD = 10**9 + 7
ans = 0
for i in range(N):
    for j in range(i, N):
        tmp = arr[j]-arr[i]
        tmp *= faster(j-i-1)
        ans += tmp
    ans%=MOD
print(ans)

하지만 이런 나이브한 풀이는 입력값이 많으면 시간초과된다.
더 개선된 풀이방식이 필요한데, 조합식을 구성하다 머리가 터져버려서 풀이를 확인하였다.

i번째 원소에 대해, i번째 원소를 최소값으로 가지는 조합의 개수와 최대값으로 가지는 조합의 개수를 비교해주면 시간을 개선할 수 잇다.

위 브루트 포스 계산식에서는 j와 i의 차를 이용하는데, 이때 i는 최소값이다.
만약 i번째 원소를 지정했을 시, 최소값일 때는 빼주고 최댓값일 때는 더하므로(양의 정수) 최댓값으로 가지는 조합의 개수 M과 최소값으로 가지는 조합의 개수 m을 뺀 만큼 곱해주면 된다.

input = open(0).readline

N = int(input())
arr = sorted(map(int, input().split()))
MOD = 10**9 + 7

pows = {i: pow(2, i, MOD) for i in range(N)}
ans = 0
for i in range(N):
    tmp = pows[i] - pows[N-i-1]
    tmp*=arr[i]
    ans = (ans+tmp)%MOD
print(ans)

조합어렵당