[c++] 61. 특정 수 만들기 (MS 인터뷰 문제 : DFS 완전탐색)
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
DFS를 사용하여 문제를 풀어야 한다.
그런데 앞서 풀었던 DFS와는 다르게 고려해야 하는 경우가 2가지가 아닌 3가지였다.
앞서 풀었던 DFS는 포함하는 경우(원소를 더함)와 그렇지 않은 경우였다.
그런데 이번 문제는 포함하는 경우에 원소를 더하는 경우뿐만 아니라 원소를 빼는 경우도 고려해야 한다.
2라는 원소를 더하는 경우, 빼는 경우, 더하지도 빼지도 않는 아무것도 하지 않는 경우이다.
위의 경우처럼 자식이 3개씩 생기게 된다.
#include <iostream>
using namespace std;
int n, m, a[11], ch[11], cnt=0;
void DFS(int L, int sum){
if(L == n+1){
if(sum == m) cnt++;
return;
}
//원소를 더하는 경우
DFS(L+1, sum+a[L]);
//원소를 계산하지 않는 경우
DFS(L+1, sum);
//원소를 빼는 경우
DFS(L+1, sum-a[L]);
}
int main(){
scanf("%d", &n);
scanf("%d", &m);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
DFS(1, 0);
if (cnt==0) printf("-1\n");
else printf("%d\n", cnt);
return 0;
}
처음에 문제를 풀 때는 앞서 푼 것처럼 그냥 더하는 경우와 아무것도 하지 않는 경우로만 재귀를 돌렸다.
그런데 그렇게 풀어보니 빼는 경우가 포함되지 않는다는 것을 알 수 있었다.
코드를 짜지는 못하고 크게 3가지 (더하는 경우, 빼는 경우, 포함하지 않는 경우)로 나눠야 한다는 것만 인지했다.
그렇게 인지를 했어도 자식을 2개가 아닌 그 이상 가지가 뻗도록 짤 수 있음을 몰랐어서 코드로는 구현하지 못한 게 아쉽다.
그러나 스스로 3가지 경우로 나눠야한다는 것을 인식했다는 것만으로도 문제에 어느 정도 많이 접근한 것 같다.
추가로 어떤 경우가 12를 만족하는 지를 출력하고 싶다는 다음과 같이 코드를 짜면 된다.
#include <iostream>
using namespace std;
int n, m, a[11], ch[11], cnt=0, path[11];
void DFS(int L, int sum){
if(L == n+1){
if(sum == m) {
cnt++;
for(int i=1; i<L; i++){
printf("%d ", path[i]);
}
puts("");
}
return;
}
//원소를 더하는 경우
path[L]=a[L];
DFS(L+1, sum+a[L]);
//원소를 계산하지 않는 경우
path[L]=0;
DFS(L+1, sum);
//원소를 빼는 경우
path[L]=-a[L];
DFS(L+1, sum-a[L]);
}
int main(){
scanf("%d", &n);
scanf("%d", &m);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
DFS(1, 0);
if (cnt==0) printf("-1\n");
else printf("%d\n", cnt);
return 0;
}