🙇‍♀️특정 수 만들기(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개가 주어진다. 각 원소는 중복되지 않는다.

▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

▣ 입력예제 1 
4 12
2 4 6 8

▣ 출력예제 1
4

🚀풀이

내가 생각한 문제 풀이 접근법은 다음과 같다.

  1. 부분 집합을 모두 구한다. (DFS)
  2. 각 부분 집합마다 +, - 경우의 수를 모두 대입해 계산한다. (DFS)
  3. 원하는 결과가 나올 때마다 카운트한다.

DFS로 부분집합을 계산한다면 그 부분집합에서도 또 DFS를 사용해 +, - 경우의 수를 세어야한다.

void DFS(int L)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		int cal = 0, cnt = 0;
		vector<int> v;
		for (int i = 1; i <= n; ++i)
		{
			if (ch[i] == 1)
			{
				v.push_back(arr[i]);
			}
		}

        // 하나의 부분집합이 만들어졌으므로 다시 이경우에 대해서 DFS
		DFS2(1, v);
		v.clear();

	}

	ch[L] = 1;
	DFS(L + 1);
	ch[L] = 0;
	DFS(L + 1);
}

void DFS2(int L, vector<int> vec)
{
	if (L > vec.size() + 1)
		return;
	if (L == vec.size() + 1)
	{
		int cal = 0;

		for (int i = 1; i <= vec.size(); ++i)
		{
            // +를 하는 경우
			if (ch2[i] == 1)
			{
				cal += vec[i - 1];
			}
            // -를 하는 경우
			else
			{
				cal -= vec[i - 1];
			}
		}

        // 원하는 결과가 나왔을 때
		if (cal == m)
		{
			res++;
		}
	}

	ch2[L] = 1;
	DFS2(L + 1, vec);
	ch2[L] = 0;
	DFS2(L + 1, vec);
}

어제 이 문제를 풀다가 생각이 안나서 오늘 다시 도전했다.

혼자 해결해서 다행인데 DFS속의 DFS이 머리가 복잡해져서 까다로운거같다.

강의를 보고 나의 코드와 비교해봐야겠다.

🚀강의를 보고 난 뒤..

강의에서는 배열의 값을 +로 넣을지 -로 넣을지 아예 넣지 않을지 이렇게 3가지 경우로 DFS를 만들었다.

나는 중첩된 DFS이지만 강의에서는 하나의 DFS로 풀 수 있었다.

강의 코드는 다음과 같다.

int n, m, res = 0;
int arr[11], ch[11];

void DFS(int L, int val)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		if (val == m)
			res++;
	}

	DFS(L + 1, val + arr[L]);
	DFS(L + 1, val - arr[L]);
	DFS(L + 1, val);
}

나보다 더 간결하고 보기도 쉬워졌다… ㅠ

DFS문제는 아직 미숙해서 많이 풀어봐야겠다.

🚀전체 코드

// + - 집어 넣기
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, res = 0, totalSum = 0;
int arr[11], ch[11], ch2[11];

void DFS2(int L, vector<int> vec)
{
	if (L > vec.size() + 1)
		return;
	if (L == vec.size() + 1)
	{
		int cal = 0;

		for (int i = 1; i <= vec.size(); ++i)
		{
			if (ch2[i] == 1)
			{
				cal += vec[i - 1];
			}
			else
			{
				cal -= vec[i - 1];
			}
		}

		if (cal == m)
		{
			res++;
		}
	}

	ch2[L] = 1;
	DFS2(L + 1, vec);
	ch2[L] = 0;
	DFS2(L + 1, vec);
}

void DFS(int L)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		int cal = 0, cnt = 0;
		vector<int> v;
		for (int i = 1; i <= n; ++i)
		{
			if (ch[i] == 1)
			{
				v.push_back(arr[i]);
			}
		}

		DFS2(1, v);
		v.clear();

	}

	ch[L] = 1;
	DFS(L + 1);
	ch[L] = 0;
	DFS(L + 1);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
		totalSum += arr[i];
	}

	DFS(1);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

강의 전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, res = 0;
int arr[11], ch[11];

void DFS(int L, int val)
{
	if (L > n + 1)
		return;
	if (L == n + 1)
	{
		if (val == m)
			res++;
	}

	DFS(L + 1, val + arr[L]);
	DFS(L + 1, val - arr[L]);
	DFS(L + 1, val);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}

	DFS(1, 0);

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고