글 읽기 - 두 배열의 합

lsk4393 4년 전 0

안녕하세요. 두 배열의 합 문제를 푸는데.. 계속 틀려서 질문드립니다 !

고수님들 부탁드릴게요 !

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long answer = 0;
long long a_size, b_size;
long long num;
vector<long long> A;
vector<long long> B;
vector<long long> A_set; // A의 부분집합
vector<long long> B_set; // B의 부분집합
long long result = 0;

void dfs(long long index, long long sum, long long check)    // 부분집합 만들기
{
	if (sum < answer)
	{
		if (check == 0)
		{
			A_set.push_back(sum);
			if (index + 1 < a_size)
			{
				dfs(index + 1, sum + A[index + 1], 0);
			}
		}
		else
		{
			B_set.push_back(sum);
			if (index + 1 < b_size)
			{
				dfs(index + 1, sum + B[index + 1], 1);
			}
		}
	}
	else
		return;
}

int main(void)
{
	cin >> answer;
	cin >> a_size;

	for (long long i = 0; i < a_size; i++)
	{
		cin >> num;
		A.push_back(num);
	}

	cin >> b_size;

	for (long long i = 0; i < b_size; i++)
	{
		cin >> num;
		B.push_back(num);
	}

	for (long long i = 0; i < a_size; i++)
		dfs(i, A[i],0 );

	for (long long i = 0; i < b_size; i++)
		dfs(i, B[i], 1);


	// 제시된 값의 개수를 찾는 로직 
	sort(A_set.begin(), A_set.end());
	sort(B_set.begin(), B_set.end());

	for (long long i = 0; i < A_set.size(); i++)
	{
		int diff = answer - A_set[i];
		auto low = lower_bound(B_set.begin(), B_set.end(), diff);
		auto up = upper_bound(B_set.begin(), B_set.end(), diff);

		result += (up - low);
	}

	cout << result << endl;

	return 0;
}

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

문제

문제

출처

ICPC

두 배열의 합

lsk4393 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말