[백준/BOJ] 백준 1208번 : 부분수열의 합 2

www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

수열을 절반으로 나눠서 앞쪽 부분 부분 수열의 합을 구하고 뒤쪽 부분 부분 수열의 합을 구한다 그리고 앞쪽 부분, 뒤쪽 부분 각각 수가 나올 때마다 앞쪽 부분은 vector<long long> front_part_to_cnt(4000001, 0)에, 뒤쪽 부분은 vector<long long> back_part_to_cnt(4000001, 0)에 해당 수를 표시하는 인덱스에(+ 2000000 한곳) 개수를 추가한다 인덱스를 4000000까지로 설정해 놓은 이유는 정수의 절댓값은 100000이고, N이 최댓값인 40일 때 그 절반인(앞쪽 또는 뒤쪽) 20개의 합의 범위는 -2000000 ~ 2000000이라서 이걸 0~4000000까지로 표현한 것이다(+2000000씩 해서) 그리고 앞쪽 부분 부분수열 합 + 뒤쪽 부분 부분 수열 합이 s인 것을 구하므로 right가 오른쪽 끝에서 시작하는 투포인터를 구현한다(중간에서 만나기?) s가 0이면 앞쪽, 뒷쪽에서 모두 안 고르는 경우가 result에 포함되었으므로 최종 결과에서 하나를 뺀다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;

int n, s;
vector<int> input_list;
vector<int> front_part;
vector<int> back_part;
//vector<int> all_part;

//인덱스를 4000000까지로 설정해 놓은 이유는 정수의 절대값은 100000이고, N이 최댓값인 40일때 그 절반인(앞쪽 또는 뒤쪽) 20개의 합의 범위는 -2000000 ~ 2000000 이라서 이걸 0~4000000까지로 표현한 것이다(+2000000씩 해서)
vector<long long> front_part_to_cnt(4000001, 0); //앞부분 수의 개수 
vector<long long> back_part_to_cnt(4000001, 0); //뒷부분 수의 개수

//앞쪽 부분의 부분 수열 합 만들기
void Make_front_part(int index, int sum)
{
	if (index == (n / 2) + 1)
	{
		front_part.push_back(sum);

		//해당 값의 개수를 센다
		front_part_to_cnt[sum + 2000000]++; //sum이 음수일 수도 있으므로 2000000을 더한 인덱스에 표시한다
		return;
	}

	Make_front_part(index + 1, sum);
	Make_front_part(index + 1, sum + input_list[index]);
}

//뒤쪽 부분의 부분 수열 합 만들기
void Make_back_part(int index, int sum)
{
	if (index == n)
	{
		back_part.push_back(sum);

		back_part_to_cnt[sum + 2000000]++;
		return;
	}

	Make_back_part(index + 1, sum);
	Make_back_part(index + 1, sum + input_list[index]);
}

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

	cin >> n >> s;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		input_list.push_back(input);
	}
	Make_front_part(0, 0);
	Make_back_part((n / 2) + 1, 0);

	sort(front_part.begin(), front_part.end());
	sort(back_part.begin(), back_part.end());

	//중복되는 수를 지운다
	front_part.erase(unique(front_part.begin(), front_part.end()), front_part.end());
	back_part.erase(unique(back_part.begin(), back_part.end()), back_part.end());

	//앞쪽 부분 부분수열 합 + 뒤쪽 부분 부분수열 합이 S인것을 구하므로
	//right가 오른쪽 끝에서 시작하는 투포인터를 구현한다
	//중간에서 만나기?
	int left = 0;
	int right = back_part.size() - 1;
	long long result = 0;

	while (left < front_part.size() && right >= 0)
	{
		if (front_part[left] + back_part[right] < s)
		{
			left++;
		}

		else if (front_part[left] + back_part[right] > s)
		{
			right--;
		}

		else if (front_part[left] + back_part[right] == s)
		{
			result += (front_part_to_cnt[front_part[left] + 2000000] * back_part_to_cnt[back_part[right] + 2000000]);
			left++;
		}
	}

	if (s == 0) //s가 0이면 앞쪽, 뒷쪽에서 모두 안고르는 경우가 result에 포함되었으므로 하나를 뺀다
		result--;

	cout << result;

	return 0;
}