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

1. 첫번째 풀이

당연히 아래처럼 itertool써서 모든 조합을 전부 구하면 그냥 짜면 시간초과가 난다

from itertools import combinations

N=int(input())
L=list(map(int,input().split()))

ans=0
for i in range(2, N+1):
    comb=list(combinations(L,i))
    for tup in comb:
        ans+=max(tup)-min(tup)

print(ans)

 

2. 두번째 풀이

문제에서 주목할 점은 "가장 큰 수"와 "가장 작은수"의 차 만을 구해주면 된다는것.

따라서 숫자를 두개씩 뽑아서 하나는 가장 큰수, 하나는 가장 작은수 로 두고, 그 사이의 숫자의 개수만큼 경우의 수를 곱해주는 식으로 구한다.

아래의 예를 통해 확인한다.

가장큰수가 6, 가장작은수가 4일때 그 사이값들을 뽑은경우와 안뽑은 경우의 수는 총 2^(2) 이므로 8이된다.

이걸 모든경우에 대해서 정리하면 아래와 같다.

2의 n승별로 묶으면 위와같은 규칙성이 보이기 때문에 적절히 구현하면 아래와 같이 된다.

N=int(input())
L=list(map(int,input().split()))
L.sort()

ans=0
for i in range(N-1):
    temp=(sum(L[-(N-1-i):])-sum(L[:N-1-i]))*(2**i)
    ans+=temp

print(ans%1000000007)

하지만 이방법은 50점.

 

3.세번째 풀이

중간에 구간별 sum을 미리 안구해놔서 그런줄 알고 구간별 sum을 구한 리스트를 추가해서 다시 시도

N=int(input())
L=list(map(int,input().split()))
L.sort()

#tosum[i] : 0부터 i까지의 합
toSum=[0 for i in range(N)]
toSum[0]=L[0]
for i in range(1,N):
    toSum[i]=toSum[i-1]+L[i]

#fromSum[i] : i에서 끝까지의 합
fromSum=[0 for i in range(N)]
fromSum[N-1]=L[N-1]
for i in range(N-2,-1,-1):
    fromSum[i]=fromSum[i+1]+L[i]

ans=0
for i in range(N-1):
    temp=(fromSum[i+1]-toSum[N-2-i])*(2**i)
    ans+=temp
    ans=ans%1000000007

print(ans)

하지만 또 50점

 

4. 네번째 풀이

제곱 수가 너무 커져서 그런것같아서 거듭제곱을 재귀로 풀어봄 (백준 1629문제 참고 : sosoeasy.tistory.com/111)

def power(a,b,c):
    if b==0:
        return 1
    if b==1 :
        return a%c
    # 짝수이면 제곱
    if b%2==0:
        return power(a**2%c,b//2,c)
    else:
        return a*power(a**2%c,b//2,c)%c


N=int(input())
L=list(map(int,input().split()))
L.sort()
num=1000000007

#tosum[i] : 0부터 i까지의 합
toSum=[0 for i in range(N)]
toSum[0]=L[0]
for i in range(1,N):
    toSum[i]=toSum[i-1]+L[i]

#fromSum[i] : i에서 끝까지의 합
fromSum=[0 for i in range(N)]
fromSum[N-1]=L[N-1]
for i in range(N-2,-1,-1):
    fromSum[i]=fromSum[i+1]+L[i]

ans=0
for i in range(N-1):
    temp=(fromSum[i+1]-toSum[N-2-i])*power(2,i,num)
    ans+=temp
    ans=ans%num

print(ans)

 

드디어 해결!