[C++] 특정 수 만들기 🔥

📄문제

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개가 주어진다. 각 원소는 중복되지 않는다.

4 12 2 4 6 8

 

⬆️ 출력

첫 번째 줄에 가능한 집합의 개수를 출력한다.

4

 

📝 풀이

#include <iostream>

int N, M, cnt = 0;
int arr[10];

void recur(int level, int sum)
{
	if (level == N + 1)
	{
		if (sum == M)
			++cnt;
	}
	else
	{
		// 다음 원소는 더하기
		recur(level + 1, sum + arr[level - 1]);

		// 다음 원소는 빼기
		recur(level + 1, sum - arr[level - 1]);

		// 다음 원소는 사용하지 않음
		recur(level + 1, sum);
	}
}

int main()
{
	scanf_s("%d %d", &N, &M);

	for (int i = 0; i < N; ++i)
		scanf_s("%d", &arr[i]);

	recur(1, 0);

	if (cnt == 0)
		printf("-1\n");
	else
		printf("%d\n", cnt);
}

• DFS를 활용하여 문제를 해결하였습니다.
• 더하기, 빼기를 활용하여 M이 나오는 경우를 찾습니다. 이 중에서 사용하지 않는 경우도 있기에 3개의 재귀를 사용하여 해결합니다.