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

 

 

조합론이 기본이 되는 문제로 계산식 발상에 좀 애먹은 문제

결론적으로 메뉴들을 맵기 순으로 정렬하면, 메뉴마다 가장 높은 수치, 낮은 수치일 경우의 수가 정해져 있으므로 각각의 메뉴마다 경우의 수를 조합론으로 구해 계산해주면 된다.

 

풀이과정

한 메뉴가 포함되는 조합의 수는 총 $2^{n-1}-1$가지이다.

하지만 스코빌 수치가 이용되는 경우만 따지면 되기 때문에 i번째 메뉴가 가장 높은 스코빌 수치일 때와 가장 낮을 때만 구해주면 된다. 식으로 나타내면 다음과 같다. (i가 0~n-1일 때)

가장 높은 스코빌 수치일 경우 >> $2^i-1$
가장 낮은 스코빌 수치일 경우 >> $2^{n-i-1}-1$
i번째 메뉴보다 높거나 낮은 스코빌을 선택할 때 모두 선택하지 않은 경우의 수가 있기 때문에 -1을 해줌

 

$2^n$을 구할 때 n이 300,000까지 일 경우 $O(n^2)$으로는 시간 초과가 나기 때문에 이를 다음 2 방법으로 처리해주면 된다.

1. 거듭제곱을 활용한 분할정복 $O(nlogn)$
2. dp로 전처리 $O(n)$

 

거듭제곱을 활용한 분할정복으로 2의 배수 계산 $O(nlogn)$

#define MOD 1000000007
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll d[3000001];

ll power_n(ll val, int time) {
	if (time == 1)return val;
	if (time % 2 == 1)return (power_n(val * val % MOD, time / 2) * val) % MOD;
	else return power_n(val * val % MOD, time / 2) % MOD;
}

int main()
{
	int n;
	ll dap = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%lld", &d[i]);
	sort(d, d + n);
	for (int i = 0; i < n; i++) {
		if (i != 0)dap += (d[i] * (power_n(2, i) - 1)) % MOD + MOD;
		if (i != n - 1)dap -= (d[i] * (power_n(2, n - i - 1) - 1)) % MOD;
	}
	cout << dap % MOD << endl;
	return 0;
}

 

 

dp로 2의 배수 30만까지 전처리 후 계산 $O(n)$

#define MOD 1000000007
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll d[3000001];
ll be[300001];

void prepro(int n) {
	ll temp = 1;
	for (int i = 0; i <= n; i++) {
		be[i] = temp;
		temp *= 2;
		temp %= MOD;
	}
	return;
}

int main()
{
	int n;
	ll dap = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%lld", &d[i]);
	sort(d, d + n);
	prepro(n);

	for (int i = 0; i < n; i++) {
		if (i != 0)dap += (d[i] * (be[i] - 1)) % MOD + MOD;
		if (i != n - 1)dap -= (d[i] * (be[n - i - 1] - 1)) % MOD;
	}
	cout << dap % MOD << endl;
	return 0;
}