[백준 15824] 너 봄에는 캡사이신이 맛있단다 (Kotlin)

🏆 문제 난이도
- Gold II

🔗 문제 링크
https://www.acmicpc.net/problem/15824

📝 문제 분석 & 접근

일단 모든 조합을 직접 만들어서 계산하는거는 불가합니다. 시간초과 이슈~

따라서, 각 봉우리의 높이(값)가 전체 합에 얼마나 기여하는지를 따로 계산해서 더해주는 방식으로 접근해야 합니다.

---

✨ 핵심 아이디어

- 봉우리의 기여도 계산하기

정렬된 배열에서 각 봉우리가 최대값이 되는 경우와 최소값이 되는 경우를 계산하여 전체 합에 더해줍니다.

• 봉우리 arr[i]가 조합의 최대값이 되는 경우: arr[i]를 포함하고, arr[0]부터 arr[i-1]까지의 i개 봉우리들 중에서 나머지 봉우리를 선택해야 합니다. 즉, i개의 봉우리로 만들 수 있는 모든 조합의 수는 2^i개입니다. 따라서 arr[i]는 2^i번 최대값이 됩니다.
• 봉우리 arr[i]가 조합의 최소값이 되는 경우: arr[i]를 포함하고, arr[i+1]부터 arr[n]까지의 봉우리들 중 나머지 봉우리를 선택해야 합니다. 남은 봉우리의 수는 n - i - 1개이므로, 이 봉우리들로 만들 수 있는 모든 조합의 수는 2^(n-i-1)개입니다.
  따라서 arr[i]는2^(n-i-1)번 최소값이 됩니다.

최종적으로, 각 봉우리 arr[i]가 전체 차이의 합에 기여하는 값은 다음과 같습니다.

(최대값이 되는 경우의 수) ×arr[i] - (최소값이 되는 경우의 수) ×arr[i]

=(2(i−1)×arr[i])−(2(n−i)×arr[i])

이를 i가 1부터 n까지 모든 봉우리에 대해 더해주면 최종 답을 얻을 수 있습니다.

---

💻 코드

import java.io.StreamTokenizer

const val MOD = 1000000007

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextLong(): Long {
        nextToken()
        return nval.toLong()
    }

    val n = nextLong().toInt()
    val arr = LongArray(n+1)
    val pows = LongArray(n+1)
    pows[0] = 1

    for(i in 1..n) {
        arr[i] = nextLong()
        pows[i] = pows[i-1] * 2 % MOD
    }

    arr.sort()

    var ans = 0L
    for (i in 1..n) {
        ans += (pows[i-1] - pows[n-i]) * arr[i]
        ans %= MOD
    }

    println(ans)
}