[백준] 15824: 너 봄에는 캡사이신이 맛있단다 - JAVA

in Algorithm on 수학

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

풀이

매운 정도를 배열로 입력받아 몇 개를 선택하여 조합을 만들 경우 그 안에서 최댓값과 최솟값의 차이가 그 조합의 맛의 정도가 된다.

이런 맛의 정도들의 합을 구하는 문제이다.

먼저 입력받은 배열을 정렬했다.

i번째 인덱스의 경우 이 값이 최솟값이 되는 경우는 2^i개의 경우,

이 값이 최댓값이 되는 경우는 2^(N - i - 1)개의 경우가 된다.

2의 거듭제곱을 구하기 위해 분할정복을 이용했다.

메모리: 58472KB

시간: 792ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1_000_000_007;
    static long[] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        dp = new long[N + 1];
        dp[0] = 1;
        long ans = 0;
        for (int i = 0; i < N; i++) {
            ans += arr[i] * pow(i);
            ans -= arr[i] * pow(N - i - 1);
            ans %= MOD;
        }

        System.out.println(ans);
    }

    public static long pow(int x) {
        if (dp[x] != 0) {
            return dp[x];
        }
        long half = pow(x / 2);
        if (x % 2 == 0) {
            return dp[x] = half * half % MOD;
        }
        return dp[x] = half * half * 2 % MOD;
    }

}