골드2 - 백준 1208 부분수열의 합 2

백준 1208 부분수열의 합 2

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

접근방법

이 문제는 방법이 떠오르지 않아서 풀이를 참고해서 풀었다.
40개의 수로 모든 조합을 구하려면 수가 너무 커서 시간초과가 발생한다. 따라서 N을 반으로 나누어서 각각의 모든 조합을 구하고 양쪽에서 구해진 조합을 합치면 답을 구할 수 있었다.

풀이

반은 front_num에 저장하고 나머지는 back_num에 저장하여서 각각 모든 합의 조합을 구해주어 해시맵을 이용한 자료구조에 담아주었다. 추가로 아무것도 선택하지 않은 경우로 0을 1씩 추가해주었다.
front_num의 조합이 담긴 fm 해시맵을 처음부터 확인하면서 합이 S가 되는 수를 back_num의 조합인 bm에서 찾아주어 경우의 수를 구해 cnt에 더해주었다.
만약 S가 0일 경우에는 fm, bm에서 아무것도 선택되지 않아 0,0이 선택되는 조합이 있기 때문에 cnt에서 1을 빼주어 값을 출력해주었다.

코드

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> front_num;
vector<int> back_num;
unordered_map<int, long long> fm;
unordered_map<int, long long> bm;

void combinationF(int sum, int start)
{
	for (int i = start; i < front_num.size(); i++)
	{
		fm[sum + front_num[i]] = fm[sum + front_num[i]] + 1;
		combinationF(sum + front_num[i], i + 1);
	}
}

void combinationB(int sum, int start)
{
	for (int i = start; i < back_num.size(); i++)
	{
		bm[sum + back_num[i]] = bm[sum + back_num[i]] + 1;
		combinationB(sum + back_num[i], i + 1);
	}
}

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

	int N, S;
	cin >> N >> S;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		if (i < N / 2)
			front_num.push_back(temp);
		else
			back_num.push_back(temp);
	}

	fm[0] = 1;
	bm[0] = 1;
	combinationF(0, 0);
	combinationB(0, 0);

	long long cnt = 0;
	for (pair<int, int> i : fm)
		cnt += i.second * bm[S - i.first];

	if (S == 0)
		cnt--;
	cout << cnt << endl;
	return 0;
}