특정 수 만들기(MS 인터뷰, DFS 완전탐색) / 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개가 주어진다. 각 원소는 중복되지 않는다.

 

▣ 출력설명

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

 

▣ 입력설명

4 12 2 4 6 8

 

▣ 입력설명

4

 

<내 코드>

몰라

또 몰라

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdbool.h>

int n, m, cnt = 0;
int num[11];
bool flag = false;

void dfs(int L, int sum) {
	if (L == n + 1) {
		if (sum == m) {
			cnt++;
			flag = true;
		}
		return;
	}
	else {
		dfs(L + 1, sum + num[L]);
		dfs(L + 1, sum - num[L]);
		dfs(L + 1, sum);
	}
}

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

dfs 함수로 들어갈때 3가지 케이스가 있다.

 

첫번째로 다음 num[L]을 더하는 케이스,

 

두번째로 다음 num[L]을 빼는 케이스,

 

마지막으로 다음 num[L]을 무시하는 케이스이다.

 

이런 방식으로 하면 모든 케이스를 빼먹지 않고 고려할 수 있다.

 

.

 

계속 이진트리만 사용하다보니까 3가지로 나눈다는 생각도 해보지 못함...

 

---

위 예시에서 cnt++가 되는 경우의 원소들을 알아보면 다음과 같다.

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdbool.h>

int n, m, cnt = 0;
int num[11];
int path[11];
bool flag = false;

void dfs(int L, int sum) {
	if (L == n + 1) {
		if (sum == m) {
			cnt++;
			for (int i = 1; i < L; i++)
				printf("%2d ", path[i]);
			puts("");
			flag = true;
		}
		return;
	}
	else {
		path[L] = num[L];
		dfs(L + 1, sum + num[L]);
		path[L] = - num[L];
		dfs(L + 1, sum - num[L]);
		path[L] = 0;
		dfs(L + 1, sum);
	}
}

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

 

<결과>

성공한 케이스마다 어떤 원소를 가지는지 알 수 있다.

 

이 코드를 참고하면 dfs함수를 이해하는데 도움이 될듯