[백준 C++] 15824번: 너 봄에는 캡사이신이 맛있단다

1. 문제

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

 

2. 알고리즘 분류

• 수학
• 정렬
• 조합론
• 분할 정복을 이용한 거듭제곱

 

3. 소스 코드

#include <iostream>
#include <algorithm>
#define MAX_N 300000

using namespace std;

typedef long long ll;
ll scovile[MAX_N];
ll MOD = 1000000007;

// binary exponentiation 알고리즘
ll binpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	ll sum = 0;

	// N : 메뉴 갯수 입력
	cin >> N;

	// 메뉴 스코빌 지수 입력
	for (int i = 0; i < N; i++)
		cin >> scovile[i];

	// 오름차순으로 정렬
	sort(scovile, scovile + N);

	/*
	* input 값이 아래와 같은 경우,
	* 6
	* 1 4 5 5 6 10
	* 
	* 해당 스코빌 지수 값이 최소값인 경우와 최대값인 경우의 수를 구하여 모든 경우의 수 합을 구할 수 있다.
	* 예를 들어,
	* 최댓값이 10인 경우의 수는 2^5 - 1개다. 결국 최댓값인 10이 2^5 - 1번 더해질 것이다.
	* 최솟값이 10인 경우의 수는 0 개다. 결국 최소값이 10이 0번 빼질 것이다.(최소 2개 이상 선택해야하므로 경우의 수는 0개다.)
	* 
	* 최댓값이 6인 경우의 수는 2^4 - 1개다. 결국 최댓값인 6이 2^4 - 1번 더해질 것이다.
	* 최솟값이 6인 경우의 수는 2^1 - 1개다. 결국 최소값인 6이 2^1 - 1번 뺴질 것이다.
	* 
	* 결론적으로 scovile[i] * (최댓값이 scovile[i]인 경우의 수) - scovile[i] * (최솟값이 scovile[i]인 경우의 수)를 매번 더한 값이 된다.
	* 이와 같이 정리할 수 있다. sum += scovile[i] * ((2^i - 1) - (2^(N - i - 1) - 1)
	* sum += scovile[i] * (2^i - 2^(N - i - 1))
	*/
	for (int i = 0; i < N; i++) {
		ll max_count = binpow(2, i);
		ll min_count = binpow(2, N - i - 1);
		sum += scovile[i] * (max_count - min_count);
		sum %= MOD;
	}

	// 정답 출력
	cout << sum;

	return 0;
}

 

4. 유용한 알고리즘

 1) 분할 정복을 이용한 거듭제곱

// binary exponentiation 알고리즘
ll binpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = (res * a);
		a = (a * a);
		b >>= 1;
	}
	return res;
}