이러한 문제에 도달했을때 즉시 종료할수있다면 하는것이 좋을까요?

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

Kyungbin Ryu

작성한 질문수

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

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

작성

231

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, i, arr[11], total=0;
bool flag = false;

void DFS(int level, int sum){
	if(sum > total/2){
		return;
	}
	if(level == n+1){
		if(sum == (total-sum)){
			flag = true;
			return;
		}
	} else {
		DFS(level+1, sum+arr[level]);
		DFS(level+1, sum);
	}
}

int main(){
	//freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &arr[i]);
		total += arr[i];
	}
	if(total%2 == 1){
		printf("NO");
		return 0;
	}
	DFS(1, 0);
	if(flag){
		printf("YES");
	} else {
		printf("NO");	
	}
	
	return 0;
}

선생님 말씀대로 코드를 짰는데요 우선 total%2 == 1 (홀수)이면 즉시 종료하는것으로 하는건 좋은 답일까요 안좋은 답일까요?

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

퀴즈

67%나 틀려요. 한번 도전해보세요!

재귀 함수가 호출될 때, 함수의 지역 변수, 매개변수, 복귀 주소 등의 정보는 어떤 자료구조에 저장되어 관리될까요?

큐 (Queue)

스택 (Stack)

배열 (Array)

연결 리스트 (Linked List)

답변 1