[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 15824번 _ 너 봄에는 캡사이신이 맛있단다

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

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

[문제]

주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.

'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.

그림1. 고추처럼 보이지만 문제와는 무관합니다.

최근 주헌이에게 좋아하는 매운맛 전문점이 생겼다. 메뉴가 아주 다양한 이 음식점은 모든 메뉴의 스코빌 지수를 명시한 메뉴판을 제공한다. 주헌이의 목표는 이 음식점의 모든 음식 조합을 먹어보는 것이다. 하지만 주헌이는 까다로워서 한 번 먹어본 조합은 다시 먹지 않는다.

이 음식점의 모든 조합을 먹어 볼 때 주헌이가 즐길 수 있는 주헌고통지수의 합을 구해보자.

 

[입력]

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

[출력]

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

 

[아이디어]

1) 각 메뉴의 스코빌 지수를 정렬하면 index 정보를 통해 각 메뉴를 최소 혹은 최대로 하는 조합의 수를 구할 수 있다.

2) 1)을 활용해 2중 for문이 아니라 O(n) 안에 해결해야 두 가지 서브태스크가 모두 통과된다.

3) i번째(1~n)로 매운 메뉴를 최소값으로 가지는 조합의 수는 2**(n-i) -1개, 최댓값으로 가지는 조합의 수는 2**(i-1)-1개이다. (0-index 주의)

4) s[i]의 값이 최소일 때는 주헌고통지수에 음수로 더해지고, 최대일 때는 양수로 더해지므로 두 조합의 수의 차에 s[i]를 곱해 정답에 더해준다.

 

# 50점
n=int(input())
s=sorted(map(int,input().split()))
ans = 0
d=10**9+7
for i in range(n-1):
    for j in range(i+1,n):
        ans+=(s[j]-s[i])*pow(2,j-i-1,d)
        ans%=d
print(ans)

많아봐야 450만개라 처음에는 이중 for문으로도 해결이 가능하다고 생각했는데, 두 번째 서브테스트에 대해서는 시간초과가 났다.

n=int(input())
s=sorted(map(int,input().split()))
ans = 0
d=10**9+7
for i in range(n):
    ans += s[i]*(pow(2,i,d)-pow(2, n-i-1,d))
print(ans%d)

위처럼 조금만 더 생각하면 s[i]를 중심으로 이루어지는 모든 연산을 한 번에 처리 할 수 있다.