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

문제

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

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

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

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

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

입력

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

출력

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

 

 

---

풀이

0. "모든 조합을 찾아보자..." -> 2^300000, 당연히 안 된다. 즉, 관점을 바꿔서 생각해야 한다: 각각의 조합마다 가장 작은 원소, 큰 원소를 찾아 빼는 대신, 특정 원소를 기준으로 그 원소가 조합에서 가장 큰 원소일 경우, 가장 작은 원소일 경우가 몇 가지인지 세보도록 한다.

1. 한 개의 원소가 선택되는 경우: 최댓값 - 최솟값 = 0이니 신경쓰지 않아도 된다.

2. 주어진 스코빌 지수를 오름차순으로 정렬한다. i번째로 작은 원소가 가장 작은 원소가 되는 경우의 수는?

    1) 가장 작은 원소가 자기가 되는 경우: 0, 1, 2, ..., i-1번째로 작은 원소는 선택되면 안 된다.

    2) i+1, ... , N번째 원소는 최소한 한 개는 선택되어야 한다: 2**(N-i-1) - 1가지라는 결론이 나온다.

3. 반대로, i번째로 작은 원사가 가장 큰 원소가 되는 경우의 수는?

    1) 자기보다 큰 원소는 선택되면 안되며,

    2) 0, 1, 2, ..., i-1번째 원소는 최소한 한 개 선택되어야 한다: 2**i - 1 가지라는 결론이 나온다.

 

따라서, i번째의 원소를 nums[i]라고 한다면, 정답에서 nums[i] * {(2**i - 1) - (2**(N-i-1) - 1)} 만큼이 더해지고 빼진다.

분할정복을 이용하여 빠르게 거듭제곱을 할 필요가 있다.

정답에서 모듈러 값을 잘 취해주면서 원하는 범위 내로 정답을 구하면 된다. 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Baekjoon15824_너봄에는캡사이신이맛있단다 {
	static final int PRIME = 1_000_000_007;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		long ans = 0;
		
		ArrayList<Long> nums = new ArrayList<Long>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			nums.add(Long.parseLong(st.nextToken()));
		}
		
		// 정렬: mergesort 쓰기 위해 List형으로 선언
		Collections.sort(nums); 
		
		for (int i = 0; i < N; i++) {
			ans = (ans + nums.get(i) * ((power(2, i)-1) - (power(2, N-1-i)-1)) % PRIME) % PRIME;
		}
		
		
		// JAVA의 모듈러 연산상 한 번은 해 줘야 한다.
		System.out.println((ans + PRIME) % PRIME);
	}
	
	// 애매하다 싶으면 long으로 선언하고 보자.
	static long power(long num, int p) {
		if (p == 0) return 1;
		
		long temp = power(num, p/2);
		if (p % 2 == 1) return ((temp * temp) % PRIME) * num % PRIME;
		else return temp * temp % PRIME;
	}
}

 

 

P.S.

어릴 적 '동백꽃'을 읽을 땐 왜 점순이가 괴롭히는지 (주인공마냥) 나도 몰랐다ㅋㅋ