너 봄에는 캡사이신이 맛있단다 (15824번) - 백준 (BOJ)

https://www.acmicpc.net/problem/15824

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

 

 

백준 - 너 봄에는 캡사이신이 맛있단다 (15824번)

 

난이도 : Gold 2

알고리즘&자료구조 : Prefix Sum (누적합)

Time Complexity : O( NlogN )

 

 

class Spicy():
    def __init__(self, N):
        rem = 1_000_000_007
        peppers = sorted(map(int, input().split()))
        for i in range(1, N):
            peppers[i] = (peppers[i-1]+peppers[i]) % rem
        self._sum_up(N, rem, peppers)
    
    
    def _sum_up(self, N, rem, peppers):
        answer = 0
        double = 1
        for i in range(N-1):
            answer += (peppers[-1] - peppers[i] - peppers[-2-i]) * double
            answer %= rem
            double = (double<<1) % rem
        self.tot_gap = answer


if __name__ == '__main__':
    spicy_comb = Spicy(int(input()))
    print(spicy_comb.tot_gap)

 

 

주어진 캡사이신 농도들을 정렬하고,

누적합을 활용해서 풀 수 있는 문제이다.

 

---

 

①  주어진 캡사이신 농도들을 오름차순으로 정렬해서 peppers에 저장한다.

peppers = sorted(map(int, input().split()))

 

 

 

② peppers의 누적합 리스트를 만든다.

for i in range(1, N):
    peppers[i] = (peppers[i-1]+peppers[i]) % rem

 

 

 

③ 모든 조합의 각 경우의 수에서, 캡사이신 농도 차이를 구하고 더해준다.

 

문제 예제 입력 2번)
1 4 5 5 6 10

간격 1 : (1 4) (4 5) (5 5) (5 6) (6 10) ▶ [ (4 + 5 + 5 + 6 + 10) - (1 + 4 + 5 + 5 + 6) ] * 2^0
= [ (4~10 까지 구간합) - (1~6 까지 구간합) ] * 2^0
○ (1 4 5 5 6 10) - (1 4 5 5 6 10)

간격 2 : (1 5) (4 5) (5 6) (5 10) ▶ [ (5 + 5 + 6 + 10) - (1 + 4 + 5 + 5) ] * 2^1

간격 3 : (1 5) (4 6) (5 10) ▶ [ (5 + 6 + 10) - (1 + 4 + 5) ] * 2^2

간격 4 : (1 6) (4 10) ▶ [ (6 + 10) - (1 + 4) ] * 2^3

간격 5 : (1 10) ▶ [ (10) - (1) ] * 2^4
→ 양 끝의 1과 10을 고정시키고, 중간의 (4, 5, 5, 6)으로 만들 수 있는 경우의 수 : 2^4 = 16
→ (캡사이신 최댓값 - 최솟값) = (10 - 1) = 9
→ 따라서, 9 * (2^4) = 144
→ 위 과정을 간격 1, 2, 3, 4에도 동일하게 적용해서 모두 더해주면 307이 나온다.

 

중간중간 rem = 1_000_000_007 로 잘 나눠줘야 한다.

answer = 0
double = 1
for i in range(N-1):
    answer += (peppers[-1] - peppers[i] - peppers[-2-i]) * double
    answer %= rem
    double = (double<<1) % rem

 

 

 

④ answer 값을 출력해준다.