백준 / 15824 / 너 봄에는 캡사이신이 맛있단다 / 파이썬, python, pypy

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

 

문제를 보면 모든 조합을 구해야한다. 

그러나 조합의 경우 O(2^N)이 되므로 시간 초과가 될 문제이므로 다른 방법을 생각해야했다. 

 

일단 식을 먼저 세우고 어떤식으로 풀어야할지 생각했을 때

 

(2, 5), (5, 8), (2, 8), (2, 5, 8)

=> 3 + 3 + 6 + 6 => 18

 

결국 정답은 모든 조합에서 (조합 안에서 최대값 - 조합 안에서 최소값)을 구해서 더하는 것이다

 

다시 말하면 

1번 조합의 최댓값 + 2번 조합의 최댓값 + .... + 마지막 조합의 최댓값 

- (1번 조합의 최솟값 + 2번 조합의 최솟값 + .... + 마지막 조합의 최솟값) 을 구하는 문제인 것이다.

 

각 조합의 최댓값 - 각 조합의 최솟값은 (각 숫자가 최댓값일 경우 - 각 숫자가 최솟값 일 경우) * 현재 숫자로 표현 가능하다.

 

그러므로 숫자들을 정렬하여 [2, 5, 8]로 만든다면

2번이 최댓값 일 경우 = []으로 만드는 조합의 경우 = 2^0 = 1

2번이 최솟값일 경우 = [5, 8]로 만드는 조합의 경우 = 2^2 = 4

 

5번이 최댓값 일 경우 = [2]로 만드는 조합의 경우 2^1 = 2,

5번이 최솟값일 경우 = [8]로 만드는 조합의 경우 = 2^1 = 2

 

8번이 최댓값 일 경우 = [2, 5]로 만드는 조합의 경우 = 2^2 = 4

8번이 최솟값 일 경우 = []로 만드는 조합의 경우 = 2^0 = 1

 

2 * (1 - 4) + 5 * (2 - 2) + 8 *(4 - 1) = -6 +0 + 24 = 18

 

그리고 파이썬의 pow를 썼을 때, 50점이 나와 pow를 분할정복으로 바꿔서 구현했더니 250점이 나왔다.

 

import sys
MOD = 1000000007
 
def pow(a, b):
    if b == 0:
        return 1
    if b == 1:
        return a
    
    half = pow(a, b//2)
    return half * half % MOD if b % 2 == 0 else half * half * a % MOD
 
N = int(sys.stdin.readline())
arr = sorted(list(map(int, sys.stdin.readline().split())))
answer = 0
 
for i in range(N):
    answer += arr[i] * (pow(2, i) - pow(2, N - i - 1))
 
print(answer % MOD)