1208 부분수열의 하1 2

알고리즘

• 수를 두개 집합으로 나눔.

• 나눈 집합 각각에 대해 모든 경우를 살펴봐서 각 집합 내부에서 s에 도달한 횟수를 세고, 만들 수 있는 수와 그 수가 나온 횟수를 센다.

• 위에서 센 횟수로, 양 집합에서 만들 수 있는 수가 a, b이고, 이 a, b가 각 집합에서 나온 횟수를 c, d라고 하면,

  a + b = s 일때, c * d만큼의 수를 전체 경우의 수에 더한다.

• 이때 save 배열을 set으로 구현한다면 메모리 사용량이 대폭 줄어든다.(각 집합이 최대 20개이니, 나올 수 있는 수의 개수는 2^20개로, 대략 100만개이므로, 현재보다 1/4로 줄일 수 있음)

  • 근데 귀찮으니 패스

코드

#include <iostream>

typedef long long ll;
using namespace std;

int n, s, num[40], last, save[2][4000001];
ll ans;

void dp(int cur, int acc, bool isPut);

int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> num[i];

	last = n;
	if (n > 20) {
		dp(20, 0, false);
		last = 20;
	}
	dp(0, 0, false);

	for (int i = 0; i <= 4000000; i++) {
		int t = s - i + 4000000;
		if (t <= 4000000)
			if (save[0][i] && save[1][t])
				ans += (ll)save[0][i] * (ll)save[1][t];
	}

	cout << ans;
}

void dp(int cur, int acc, bool isPut) {
	if (cur == last) {
		if (isPut) {
			if (cur > 20)
				save[1][acc + 2000000]++;
			else
				save[0][acc + 2000000]++;
			if (acc == s)
				ans++;
		}
		return;
	}

	dp(cur + 1, acc + num[cur], true);
	dp(cur + 1, acc, isPut);

	return;
}