[알골90제] 61번 - 특정 수 만들기 : DFS (MS인터뷰)

* 문제

 

N개의 원소로 구성된 자연수 집합이 주어짐

집합의 원소와 +, - 연산을 사용하여 특정수인  M을 만드는 경우가 몇가지 있는지 출력하시오.

각 원소는 연산에 한번만 사용한다.

 

- 입력예제

4 12

2 4 6 8

=> 원소 4개로 + -를 조합하여 12를 만드는 경우의 수는 몇가지? 경우가 없다면 -1 출력

 

 

 

* 문제 풀이

 

2를 보면 +2 -2 X 와 같은 3가지 경우 적용가능

4도 마찬가지 +4 -4 X 와 같은 3가지 경우 적용 가능

 

-2 +6 +8 = 12 은 어떻게 나오나?

깊이 탐색으로 모든 경우의 수 탐색해서 가능 => 완전탐색

- 레벨 5되고 종료!

 

* 코드 구현

//61번 - 특정 수 만들기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
int n, m, a[11], count = 0;

void DFS(int L, int val) {

	if (L == n + 1) {
		if (val == m) count++;
	}
	else {
		DFS(L + 1, val + a[L]);
		DFS(L + 1, val - a[L]);
		DFS(L + 1, val); //얘를 빼먹음
	}
}

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	DFS(1, 0);

	if (m == 0) printf("-1");
	else printf("%d", count);

	return 0;

}

 

+ 특정 수 찾은 원소들 보여주기 추가

//61번 - 특정 수 만들기
//+경우의 수 식 모두 출력하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
int n, m, a[11], count = 0, path[11];

void DFS(int L, int val) {

	if (L == n + 1) {
		if (val == m) {
			count++;
			for (int i = 1; i < L; i++) {
				printf("%d ", path[i]);
			}
			puts("");
		}
	}

	else {
		path[L] = a[L];
		DFS(L + 1, val + a[L]);

		path[L] = -a[L];
		DFS(L + 1, val - a[L]);

		path[L] = 0;
		DFS(L + 1, val); //얘를 빼먹음
	}
}

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	DFS(1, 0);

	if (m == 0) printf("-1");
	else printf("%d", count);

	return 0;

}

 

 

 

완전탐색에 관하여,,

 

https://brenden.tistory.com/10

[알고리즘] 완전탐색