질문 있습니다!!

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

60. 합이 같은 부분 집합 (아마존 인터뷰 문제 : DFS 완전탐색)

작성

185

^ㄹ

#include <iostream>
#include<string>
#include<vector>
#include<deque>
#include<algorithm>
#include<stack> //스택 구조 사용하기
using namespace std;

///////////////////////////////////////////////////////////////
//변수 정의(전역변수)
int N;
int sum = 0;
bool arr[11];
int vec[11];
//vector<int>vec;
///////////////////////////////////////////////////////////////
//내가 짠 함수(시간 오래 걸림)
//void func(int k)
//{
//	int S = 0;
//	for (int i = 1; i <= N; i++)
//	{
//		if (arr[i] == true)
//		{
//			S += vec[i];
//		}
//	}
//
//	if (sum  - S == S)
//	{
//		cout << "YES" << '\n';
//		exit(0);
//	}
//
//	if (k > N)
//	{
//		//cout << "NO" << endl;
//		return ;
//	}
//
//	else
//	{
//		arr[k] = 1;
//		func(k + 1);
//		arr[k] = 0;
//		func(k + 1);
//	}
//}
////////////////////////////////////////////////////////////
//강의 듣고 다시 짠 함수
void func(int k, int S)
{
	if (sum - S == S)
	{
		cout << "YES" << '\n';
		exit(0);
	}

	if (k > N)
		return;
	else
	{
		func(k + 1, sum + vec[k]);
		func(k + 1, sum);
	}
}
/////////////////////////////////////////////////////////////
//main 함수
int main()
{
	ios::sync_with_stdio(0);
	cin >> N;
	
	for (int i = 1; i <= N; i++)
	{
		cin >> vec[i];
		sum += vec[i];
	}

	func(1, 0);

	cout << "NO" << endl;
	return 0;
}

C++코테 준비 같이 해요!

답변 2

김나다

저도 궁금한데 아직도 답변이 안달려있네요 ㅠㅠ

leehoogwan

질문자

안녕하세요! 강의 정말 잘 듣고 있습니다!!

질문이 두 가지 있어서 여쭙니다.

(제가 짠 함수는 일단 주석처리를 했습니다.)

선생님 강의를 보고 다시 짠 코드는 함수의 매개변수를 늘려 시간을 줄인 점이라 생각합니다.

1. 질문) 저는 if(L == n+1)일 때 조건을 확인하지 않고 그 전에 따로 확인해줘서 exit(0)를 넣어 찾으면 강제종료 되도록 구현했습니다. 왜냐면, 이게 가능한지 안한지의 경우만 찾으면 되기 때문에 끝까지 안돌아도 중간에 확인해서 조건을 만족하면 강제종료 해도 된다고 생각했습니다.

여기서 예외나 오류가 생길 수 있을까요?

2. 질문) 제가 vector를 쓰고 싶어서 전역변수로 잡고(vector<int>vec) <-- 이렇게

main()안에서 N의 크기를 넣어 다시 정의해 주면서(vector<int>vec(N)) <--이렇게

push_back으로 입력을 받았는데 자꾸 실행하면 오류가 나오네요..ㅜ 예외처리의 문제라고 뜨는데, 혹시 전역변수로 정의하고 main()에서 또 정의해주게 되면 문제가 생기는 것일까요?.. 아니면 단순 데이터 범위를 제가 넘은걸까요?..확인하고 또 확인했는데도 모르겠네요ㅜ .

감사합니다.

인프런 커뮤니티 질문&답변

질문 있습니다!!