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

김혁수

작성한 질문수

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

61. 특정 수 만들기 (MS 인터뷰 문제 : DFS 완전탐색)

질문있습니다

작성

165

61번 문제를 다르게 풀었는데 오류가 발생했습니다.

주어진 문제를 예시로 들자면 (2,4,6,8) 4개의 배열을 늘려서 (2,4,6,8,-2,-4,-6,-8) 8개로 선언한 뒤 DFS 함수를 사용했는데 답이 틀렸습니다.

스스로 디버그를 거쳤지만 오류를 발견하지 못했는데 무엇이 문제인가요?ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

int cnt=0, n, m, a[22];

void DFS (int L, int sum){
	if(L == n+n+1){
		if(sum == m) cnt++;
	}
	else {
		DFS(L+1,sum + a[L]);
		DFS(L+1,sum);
	}
}

int main() {
	
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1; i<= n+n; i++){
		if(i <= n) scanf("%d",&a[i]);
		else a[i] = -(a[i-n]);
	}
	
	DFS(1,0);
	
	printf("%d",cnt);
	
	return 0;
}

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

답변 1

김태원

지식공유자

안녕하세요^^

전역변수로 n, m을 잡았으면 main 함수에서 지역변수 선언을 하면 안됩니다.

그리고 아래 코드처럼 해서 path를 출력해보면 중복해서 개수를 카운팅하는 것을 알 수 있을 겁니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>

using namespace std;

int cnt=0, n, m, a[22], path[20];

void DFS (int L, int sum){
	if(L == n+n+1){
		
		if(sum == m){
			cnt++;
			for(int i=1; i<L; i++) printf("%d ", path[i]);
			printf("\n");
		}
		
	}
	else {
		path[L]=a[L];
		DFS(L+1,sum + a[L]);
		path[L]=0;
		DFS(L+1,sum);
	}
}

int main() {
	freopen("input.txt", "rt", stdin);
	//int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1; i<= n+n; i++){
		if(i <= n) scanf("%d",&a[i]);
		else a[i] = -(a[i-n]);
	}
	
	DFS(1,0);
	
	printf("%d",cnt);
	
	return 0;
}

김혁수

작성한 질문수

전체 Q&A

질문하기