[Python] 백준 15824 - 너 봄에는 캡사이신이 맛있단다
주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.
'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.
그림1. 고추처럼 보이지만 문제와는 무관합니다.
최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다. 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.
이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.
입력
첫 줄에 메뉴의 총 개수 N이 주어진다. 두 번째 줄에는 N개의 메뉴의 스코빌 지수가 주어진다. 모든 스코빌 지수는 0보다 크거나 같고 ((2^{31}-1))보다 작거나 같은 정수이다.
출력
한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.
풀이
내 기억이 맞다면 김유정의 소설 <동백꽃>에서 점순이가 비슷한 말을 했던 것 같다.
어쨌든 문제를 풀어보자.
예제 입력 2를 통해서 설명을 해보겠다.
먼저, 가장 큰 값/가장 작은 값들을 가지고 문제를 푸는 것이니
주어진 값들을 정렬해주고 시작하는 것이 좋을 것이다(예제 입력 2는 이미 정렬된 상태다).
1, 4, 5, 5, 6, 10
여기서 각각의 수들은 조합의 개수에 따라 총합에 더해질 수도 있고, 빼질 수도 있다.
무슨 말인지 이해가 안되면 구체적인 상황을 보자.
먼저 1을 보자.
1은 항상 가장 작은 수이다. 무슨 조합을 하든 1은 빼지는 수이므로, 4, 5, 5, 6, 10으로 만들 수 있는 조합의 개수를 계산해주고 그만큼 1을 빼주면 된다.
다음은 4다.
5, 5, 6, 10으로 조합을 만들 경우 4는 가장 작은 수이므로 빼지는 수가 된다. 하지만, {1, 4}와 같이 4보다 작은 수들로 조합을 만들어서 4가 가장 큰 수가 되게 한다면, 그 조합의 개수만큼 4는 더해지게 된다.
이거를 나머지 수들에 대해서도 해주면 되는데, 전체적인 상황을 그림으로 보도록 하자.
이걸 코드로 구현하는 것은 쉬울 것이다. 알아서 구현하라.
참고로, C++ 등에서는 2의 매우 큰 거듭제곱을 구현하기 위해서 분할 정복을 이용해야한다(나중에 블로그에서 다루겠다).
그런데 python의 pow() 함수는 개꿀이다. 이거 알아서 지원해주고 심지어는 나머지 연산도 해준다. 그래서 python으로 풀면 분할 정복을 이용한 거듭제곱이 필요가 없고 코드가 깔끔해진다.
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
cnt = 0
big = 1000000007
for i in range(N):
a = pow(2, N-i-1, big) - 1
b = pow(2, i, big) - 1
cnt += -arr[i]*a + arr[i]*b
cnt %= big
print(cnt)