[백준/BOJ] 백준 1450번 : 냅색문제

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

1450번: 냅색문제

중간에서 만나는 투 포인터를 이용하여 문제를 해결했다. 입력받은 물건을 반으로 나눠서 앞쪽 물건들을 이용해 만들 수 있는 모든합과, 뒤쪽 물건들을 이용해 만들 수 있는 모든합을 구해서(이때 합이 c가 넘어가는 것은 넣지 않는다) 각각 정렬한 뒤, 앞쪽 물건들을 이용해 만들 수 있는 모든 합은 앞쪽에서 뒤쪽 물건들로 만들 수 있는 모든 합은 뒤쪽에서 시작하여 중간에서 만나는 투 포인터를 이용해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, c;
vector<int> item;
vector<int> front_sum;
vector<int> back_sum;
int result = 0;

void Make_front_sum(int index, int sum)
{
	//합이 C를 넘어갈때
	if (sum > c)
		return;

	//앞쪽 끝까지 체크 했을때
	if (index == n / 2)
	{
		front_sum.push_back(sum);
		return;
	}

	//index구간 물건을 고를때
	Make_front_sum(index + 1, sum + item[index]);

	//index구간 물건을 고르지 않을때
	Make_front_sum(index + 1, sum);
}

void Make_back_sum(int index, int sum)
{
	//합이 C를 넘어갈때
	if (sum > c)
		return;

	//뒤쪽 끝까지 체크 했을때
	if (index == n)
	{
		back_sum.push_back(sum);
		return;
	}

	//index구간 물건을 고를때
	Make_back_sum(index + 1, sum + item[index]);

	//index구간 물건을 고르지 않을때
	Make_back_sum(index + 1, sum);
}

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

	cin >> n >> c;

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

		item.push_back(input);
	}

	//앞쪽 물건들로 만들수 있는 모든 합을 구한다
	Make_front_sum(0, 0);

	//뒤쪽 물건들로 만들수 있는 모든 합을 구한다
	Make_back_sum(n / 2, 0);

	sort(front_sum.begin(), front_sum.end());
	sort(back_sum.begin(), back_sum.end());

	//중간에서 만나는 투포인터를 이용한다
	int left = 0;
	int right = back_sum.size() - 1;
	while (1)
	{
		if (left == front_sum.size()) //front_sum을 모두 체크 했을때
			break;
		if (right == -1) //back_sum을 모두 체크 했을때
			break;

		if (front_sum[left] + back_sum[right] <= c)
		{
			result += (right + 1); //front_sum[left]와 합쳐서 합이 c이하가 되는것은 back_sum의 right 인덱스 이하의 것들 모두 가능하다
			left++; //다음에 확인할 front_sum의 인덱스
		}

		else
		{
			right--;
		}
	}

	cout << result << "\n";

	return 0;
}