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

핵심은 power함수의 logN화.

 

1번 50점.

import sys
input = sys.stdin.readline

N = int(input())
menus = sorted(map(int,input().split()))
MOD = 1000000007
minus = 0
for i in range(N-1):
    for j in range(i+1,N):
        minus += ((menus[j] - menus[i])*(2**(j-i-1)))%MOD
print(minus%MOD)

 

2번 50점

N = int(input())
menus = sorted(map(int,input().split()))
MOD = 1000000007
minus = 0
plus = 0
for i in range(N):
    minus += (menus[i]%MOD)*pow(2,N-i-1,MOD)
    plus += (menus[i]%MOD)*pow(2,i,MOD)
    plus %= MOD
print((plus-minus)%MOD)

 

3번 250점 : 제곱을 재귀로 했는데 분할 정복으로 해도 될것임.

import sys
input = sys.stdin.readline

# 제곱을 재귀로.. 분할정복으로 해도 될듯?
def pow(a,b,c):
    if b==0:
        return 1
    if b==1 :
        return a%c
    if b%2==0:
        return pow(a**2%c,b//2,c)
    else:
        return a*pow(a**2%c,b//2,c)%c

N = int(input())
menus = sorted(map(int,input().split()))
MOD = 1000000007
minus = 0
plus = 0
for i in range(N):
    minus += (menus[i]%MOD)*pow(2,N-i-1,MOD)
    plus += (menus[i]%MOD)*pow(2,i,MOD)
    plus %= MOD
print((plus-minus)%MOD)