백준 15824 너 봄 캡사이신이 맛있단다.

 

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

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

 

 

스코빌 지수 배열이 주어졌을때  주헌고통지수 조합을 구하는 문제다.

주헌 고통지수는 조합이 만들어졌을때 스코빌 지수의 최대값 - 최소값이다.

예를 들어 [5,2,8] 조합을 골랐을때 주헌고통지수는 8-2 = 6이다.

 

[t0,t1,t2,t3... tn-1] 이라는 크기가 n인 스코빌 지수 배열이 있다고 가정하자. (t0<t1<t2<t3<... tn)로 정렬된 상태이다.

그렇다면 스코빌 지수의 최대값이 tn, 최소값이 t0인 조합의 갯수는 {t1.t2....,tn-2}의 부분 집합의 갯수고, 이는 2^(n-1)개이다. 

즉 (tn-t0)을 주헌고통지수를 가지는 합은 (tn - t0)*2^(n-1) 이다.

 

그러면 이렇게 식을 짤수 있다.

i= 0~(n-1) 까지

j= i+1~ (n-1)까지 for loop을 돌리면서

Σ (Σ (tj-ti) *2^(j-1-1))을 구하면된다.

하지만 이코드는 시간복잡도가 O(N^2)에 수렴하게 되고

Large의 경우 N이 30만까지 생각해야하므로 시간초과가 난다.

 

그렇다면 이렇게 생각해보자.

 

마찬가지로 t0<t1<t2<... <tn-1 로 된 스코빌 지수가 있다고 가정하자

주헌고통지수는 조합의 최대값 - 최소값이므로

주헌고통지수의 합은 (모든 조합의 최대값의 합) - (모든 조합의 최소값의 합)이다.

 

그렇다면 t0를 최소값으로 가지는 조합의 갯수는 몇개일까? 답은 2^(n-1-1+1)개이다. (t1,t2,t3....,tn-1)의 부분집합 개수이므로

t0를 최대값으로 가지는 조합의 갯수는 {} (공집합의 부분개수  2^(0 = 1개다.

t1을 최소값을 가지는 조합의 개수는 마찬가지로 2^(n-1-2+1)개이다. [ (t2,t3,t4,,,tn-1)의 부분집합 개수)]

t1를 최대값으로 가지는 조합의 갯수는 {t0}의 부분집합개수이므로 2^1 = 2이다.

 

즉 ai =

Σ(ti를 최대값으로 가지는 조합)- Σ(ti를 최소값으로 가지는 조합의)이라고 가정하면

 

ai = pow(2,i) - pow(2,n-1-i)이다.

그러므로 

Σai*ti = Σti*(pow(2,i) - pow(2,n-i-1))로 문제의 시간복잡도가 O(N)으로 줄어든다.

package 백준;

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

public class 너봄에는캡사이신이맛있단다 {
	public static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}
	}
	static ArrayList <Long> taste = new ArrayList <Long>();
	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		
		long pow[] = new long[N];
		pow[0] = 1;
		int D = 1000000007;
				
		for(int i =0 ;i<N;i++) {
			taste.add(sc.nextLong());
		}
		
		Collections.sort(taste);
		
		for(int i =0 ;i <N-1;i++) {
			pow[i+1] = (pow[i] * 2) % D;
		}
	
		long answer = 0;
		
		for(int i =0 ;i <N;i++) {
			answer = (answer + taste.get(i) * ( -pow[N-1-i]+pow[i]))%D;
		}
		System.out.println(answer);
	}

}