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

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

시간 제한 1초, 메모리 제한 512MB

# 조건

• '스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다.
• 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다.
  • 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다.
  • 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.
• 최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다.
• 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다.
• 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다.
• 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.
• 이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.

입력

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

출력

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

# 접근 방법

• 브루트포스로 푼다면 시간초과를 받게 된다.
• 따라서, 아이디어를 떠올리는 것이 어려웠다.
• 문제를 보면 알 수 있듯이 모든 조합에서 (조합 안에서의 최댓값 - 조합 안에서의 최솟값) 을 더하는 문제이다.
• 따라서 우선, 정렬을 해준다.
• 예제 2번을 1 4 5 5 6 10과 같이 정렬 되었을 때
  • 4와 6이 최소와 최댓값인 경우 가운데에는 5 5 를 뽑는 경우 안 뽑는 경우가 있으므로 4개의 경우의 수가 있다.
  • (6-4) * 2^(2) 의 식이 나와 8이라는 값을 뽑을 수 있다.
  • 이 경우를 표 정리하면 아래와 같다.

https://sosoeasy.tistory.com/346

• 2의 n승별로 묶으면 위와 같은 규칙성이 나오기 때문에 적절히 구현해주면 된다.
• 또한, 파이썬에서 큰 수 연산 곱하기의 시간 복잡도는 O(n^1.585) 정도라고 하므로 재귀를 통하여 제곱을 구해준다.

 

# 50점

• 구간 별 합을 안 구해주어서 그런지 50점을 받았다.

import sys  
sys.stdin = open('input.txt')  

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())  
nums = [*map(int, input().split())]  
mod = 1000000007  
nums.sort()  

ans = 0  
for i in range(N-1):  
    temp = (sum(nums[-(N-1-i):]) - sum(nums[:N-1-i])) * power(2, i, mod)  
    ans += temp  
    ans %= mod  


print(ans)

 

 

# 250점

• 구간 합을 미리 구해둔 후 제출하니 pass가 되었다.

import sys  
sys.stdin = open('input.txt')  

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())  
nums = [*map(int, input().split())]  
mod = 1000000007  
nums.sort()  

minus_sum = [0 for i in range(N)]  
minus_sum[0] = nums[0]  

for i in range(1, N):  
    minus_sum[i] = minus_sum[i-1] + nums[i]  

plus_sum = [0 for i in range(N)]  
plus_sum[N-1] = nums[N-1]  
for i in range(N-2, -1, -1):  
    plus_sum[i] = plus_sum[i+1] + nums[i]  


ans = 0  
for i in range(N-1):  
    temp = (plus_sum[i+1] - minus_sum[N-2-i]) * power(2, i, mod)  
    ans += temp  
    ans %= mod  


print(ans)