[BOJ] 백준 15824. 너 봄에는 캡사이신이 맛있단다 (Gold I)

아이디어에서 배울 점이 있었던 문제이다.

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

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

해결한지는 시간이 좀 됐다. 포스팅이 귀찮아서 미루었을 뿐...

Small을 해결하기 위한 상한 시간복잡도는 O(N^2)

Large를 해결하기 위한 상한 시간복잡도는 O(NlgN)임을 알 수 있다.

---

의식의 흐름 및 해설

될 수 있는 모든 조합의 [최댓값과 최솟값의 차]의 합을 구하는 문제이다.

처음에 이걸 O(N^2) 이상의 알고리즘으로 해결하는 방법밖에 떠오르지 않아 꽤 고민을 했다.

 

그런데 생각해보니 결국 모든 조합의 [최댓값과 최솟값의 차]의 합이면

모든 경우의 최댓값 - 모든 경우의 최솟값을 해주면 된다는 것을 알아챘다. 

 

이 경우를 구하는 것은 집합론을 이용하면 그나마 할만하다.

아래 예제를 보면서 생각해보자.

3
5 2 8
Ans: 18

8이 최솟값이 되는 경우는 자기 자신만 해당될 때 외엔 없다. 따라서 1가지 경우이다.

8이 최댓값이 되는 경우는 [5를 집합에 포함시킬지 안시킬지]*[2를 집합에 포함시킬지 안시킬지]이므로 2^2가지 경우이다. 실제로 (8), (5, 8), (2, 8), (5, 2, 8) 네 가지 경우가 있다.

 

따라서 일반화시키면 [i번째 수가 최댓값이 될 때 - 최솟값이 될 때 경우의 수]를 구해준다면 2^i - 2^(N-i-1) 이 됨을 알 수 있다.

 

2^300,000까지 값을 구해줘야되므로 분할정복 거듭제곱을 이용하여 오버플로, 시간초과가 나지 않도록 해주자. (다른 풀이도 있다고 하는데 나는 첨 봤을 때 이 풀이 먼저 생각났다.)

 

이 때 뺄셈의 MOD로 나눠줄 때, 이상한 값이 출력될 수 있으므로 뺄셈에선 항상 MOD를 더해준 후 MOD로 나머지를 구해주는 것을 잊지 말자.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 300001;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N;
ll ans;
vector<int> v;
ll power(ll n, ll k) {
	ll ret;
	if (k == 0)
		return 1;
	if (k == 1)
		return n;
	ret = power(n, k / 2);
	ret = ret * ret;
	ret %= MOD;
	if (k % 2)
		ret *= n;
	return ret % MOD;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(all(v));
	for (int i = 0; i < N; i++) {
		ans += v[i] * (power(2, i) + MOD - power(2, (ll)N - i - 1)) % MOD;
		ans %= MOD;
	}
	cout << ans << "\n";
}

---

오랜만에 분할정복을 이용한 거듭제곱 문제를 풀었다.

감각 유지되는 데 도움이 된 문제였다.

골드1치고 조금 쉬운 감도 없지않아 있다.