[C/C++] DFS 61. 특정 수 만들기(DFS : MS 인터뷰)

문제 풀이

N개의 원소로 구성된 자연수 집합이 주어지면, 집합의 원소와 ‘+’, ‘-’ 연산을 사용하여 특정
수인 M을 만드는 경우가 몇 가지 있는지 출력하는 프로그램을 작성하세요. 각 원소는 연산에
한 번만 사용합니다.
예를 들어 {2, 4, 6, 8}이 입력되고, M=12이면
2+4+6=12
4+8=12
6+8-2=12
2-4+6+8=12
로 총 4가지의 경우가 있습니다. 만들어지는 경우가 존재하지 않으면 -1를 출력한다.
입력설명
첫 번째 줄에 자연수 N(1<=N<=10)와 M(1<=M<=100) 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.
출력설명
만들어진 경우의 개수를 출력한다. 존재하지 않으면 -1를 출력한다.

 

소스코드

이 문제는 DFS를 사용하여 푸는 문제이다.

지난 60번과 좀 차이는 있는 데, 바로 집합에서 수를 가져다 쓸 때 마이너스를 붙여 연산할 수 있다는 것이다.

따라서, 플러스로 연산하기, 마이너스로 연산하기, 아무것도 하지 않기 이렇게 3가지의 경우가 나오게 된다.

 

그럼 이전처럼 if와 return을 적절히 섞어서 만들 수 있다.

각각마다 3가지 경우가 필요하니 DFS를 세 줄로 나누어 작성하였다.

DFS(cnt+1,sum); 집합에서 아무것도 더하지 않는 것

DFS(cnt+1,sum+arr[cnt]); 집합에서 cnt 인덱스의 값을 더하는 것

DFS(cnt+1,sum-arr[cnt]); 집합에서 cnt 인덱스의 값을 빼는 것

이렇게 세 가지 길로 DFS가 돌게 된다.

DFS 함수를 살펴보도록 하자. 해당 cnt 값에서 다시 DFS를 부르고......반복한다.

그리고 N+1번째 때 return된다. return되면 cnt-1을 사용하던 함수로 돌아가,

그 다음 함수인 DFS(cnt+1, sum-arr[cnt);로 흘러간다. 반복된다.

void DFS(int cnt, int sum)
{
	if (cnt==N+1)
	{
		if (sum==M)
		{
			flag=true;
			cnt_value++;
			return;
		}
		return;
	}
	DFS(cnt+1,sum+arr[cnt]);
	DFS(cnt+1,sum-arr[cnt]);
    DFS(cnt+1,sum);
}

그림을 보면 아래와 같다. 각 지점마다 더하는 경우, 빼는 경우, 가만히 있는 경우 세 갈래로 나누어진다.

DFS설명

#include <iostream>
#define MAX 11
using namespace std;

int N,M;
int cnt_value;
int arr[MAX];
bool flag;

void input()
{
	cin>>N>>M;
	
	for (int i=1; i<=N; i++)
	{
		cin>>arr[i];
	}
}

void DFS(int cnt, int sum)
{
	if (cnt==N+1)
	{
		if (sum==M)
		{
			flag=true;
			cnt_value++;
			return;
		}
		return;
	}
	DFS(cnt+1,sum+arr[cnt]);
	DFS(cnt+1,sum-arr[cnt]);
    DFS(cnt+1,sum);
}
	


int main() {
	
	input();
	DFS(1,0);
	
	if (flag==true)
	{
		cout<<cnt_value;
	}
	else if (flag==false)
	{
		cout<<-1;
	}
	
	return 0;
}

Reference

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