글 읽기 - 9%정도에서틀리는데 한번 봐주실 수있나요?

his130 6년 전 0

제 로직은

1.주어진 수열을 두개로 나눴습니다.

2.각각의 수열에 대해 makeAll 함수를 이용해서 부분집합의 합을 구합니다.(공집합을 제외하고)

3.두개의 합집합을 오름차순으로 정렬합니다.

4.하나의 합집합의 값을 A 라 하면 찾아야 하는 값은 s-A가 됩니다,

따라서 다른 합집합에서 s-A 값을 lower_bound 와 upper_bound 를 이용해 찾습니다.

5.그 갯수를 카운팅 합니다.

어느점에서 틀리는지 잘 모르겠습니다.

도와주세요!

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> sum1;
vector<int> sum2;
bool first;
void makeAll(vector<int> v, int k, int sum, int num)
{
	if (num == 0)
	{
		if (k == v.size())
		{
			if (first && sum == 0)
			{
				first = false;
				return;
			}
			sum1.push_back(sum);
			return;
		}

		makeAll(v, k + 1, sum + v[k],num);
		makeAll(v, k + 1, sum, num);
	}

	if (num == 1)
	{
		if (k == v.size())
		{
			if (first && sum == 0)
			{
				first = false;
				return;
			}
			sum2.push_back(sum);
			return;
		}

		makeAll(v, k + 1, sum + v[k], num);
		makeAll(v, k + 1, sum, num);
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	int n, s;
	scanf("%d%d", &n, &s);
	vector<int> v1(n/2);
	vector<int> v2(n - (n / 2));
	for (int i = 0; i < n/2; i++)
	{
		scanf("%d", &v1[i]);
	}

	for (int i = 0; i < n-(n/2); i++)
	{
		scanf("%d", &v2[i]);
	}

	first = true;
	makeAll(v1,0,0,0);
	first = true;
	makeAll(v2,0,0,1);
	
	sort(sum1.begin(), sum1.end());
	sort(sum2.begin(), sum2.end());

	int i = 0;
    long long ans = 0;
	while (i < sum1.size())
	{
		int A = sum1[i];
		int findNum = s - A;

		auto l = lower_bound(sum2.begin(), sum2.end(), findNum);
		auto u = upper_bound(sum2.begin(), sum2.end(), findNum);

		if (l != u)
		{
			ans += u - l;
		}

		i++;
	}

	printf("%lld\n", ans);

	return 0;
}

ntopia 6년 전 2

접근 자체는 괜찮은 것 같은데요,

이렇게 하면

sum1 에서만 혹은 sum2 에서만 숫자를 골라서 S를 만드는 경우를

세지 못하게 됩니다.

반례를 들자면

6 3

1 1 1 -1 -1 -1

이 있겠네요.

his130 6년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9%정도에서틀리는데 한번 봐주실 수있나요?

his130 6년 전 0

ntopia 6년 전 2

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말