[c++] 60. 합이 같은 부분 집합 (아마존 인터뷰 문제 : DFS 완전탐색)
문제
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
○ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며 그 크기는 1,000,000 이하입니다.
○ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.
○입력예제 1
6
1 3 5 6 7 10
○ 출력예제 1
YES
두 개의 부분집합으로 나누었다는 것은 선택되어지는 수의 집합과 선택되지 않는 수의 집합으로 생각하면 된다.
문제에서 예로 들은 {1, 3, 5, 7} = {6, 10} 에서는 1, 3, 5, 7이 선택이 되어진 것이고 나머지 6, 10은 그렇지 않은 것이다.
따라서 DFS를 이용하여 선택할 숫자를 골라주면 된다. 부분집합을 구하는 59번 문제와 매우 흡사하다.
선생님의 코드
#include <iostream>
using namespace std;
int n, a[11], total=0;
bool flag = false;
void DFS(int L, int sum){
if(sum>total/2) return; //sum이 total의 절반보다 커지면 두 집합의 합이 같을 수 없으므로 바로 끝냄
if(flag==true) return; //하나라도 참인 것이 나오면 끝냄
if(L == n+1){ //종료 포인트
if(sum == (total-sum)){ //두 집합의 합이 같은 경우
flag = true; //true로 바꿔줌
}
}
else{
//a[L] 원소가 집합에 들어가는 경우
DFS(L+1, sum+a[L]); //a[L]원소가 집합에 들어가는 수이므로 sum에다가 더해줌
//a[L] 원소가 집합에 들어가지 않는 경우
DFS(L+1, sum); //sum에는 더할 필요가 없음
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
total += a[i];
}
DFS(1,0); //1은 레벨이고 0은 원소의 합임
if(flag) cout << "YES" << '\n';
else cout << "NO" << '\n';
return 0;
}
59번과는 다르게 숫자들의 합을 DFS 함수의 인자로 넘기고 있다.
첫번째 DFS함수에 들어가는 경우는 트리로 보았을 때 왼쪽 자식으로 넘어가는 경우이고 이 경우는 a[L]에 해당하는 원소가 들어가는 경우이므로 sum에 바로 이 원소를 더해준다.
두번째 DFS함수에 들어가는 경우는 트리로 보았을 때 오른쪽 자식으로 넘어가는 경우이므로 이 경우는 a[L]에 해당하는 원소를 더할 필요가 없기에 그냥 넘어가면 된다.
DFS(1,0)이 호출되고 재귀적으로 DFS(L+1, sum+a[L])을 호출하면 다음 그림과 같아진다.
더 진행하면 다음과 같은 모습이다.
위의 예시에서 total 총합이 32인데 32의 절반인 16을 넘어가는 순간 두 집합의 합이 같을 리가 없으므로 바로 끝내주면 된다.
추가로 flag가 true로 된다면 두 집합의 합이 같은 경우가 나온 것이므로 바로 끝내주면 된다.
내가 푼 코드
#include <iostream>
using namespace std;
int n, arr[11], ch[11], flag, sum1, sum2;
void DFS(int L){
if(L == n+1){
sum1 = 0; //선택되어 집합에 포함된 숫자를 더할 변수, 초기화 필수
sum2 = 0; //선택되지 못하여 집합에 포함되지 않은 숫자를 더할 변수, 초기화 필수
for(int i=1; i<=n; i++){
if(ch[i]==1) sum1+=arr[i]; //선택되었으면 sum1에 더함
else sum2+=arr[i]; //선택되지 않았으면 sum2에 더함
}
if(sum1 == sum2) flag = 1;
return;
}
ch[L] = 1;
DFS(L+1);
ch[L] = 0;
DFS(L+1);
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
}
DFS(1);
if(flag) cout << "YES";
else cout << "NO";
return 0;
}위의 코드는 내가 처음에 풀었던 코드이다.
부분집합을 구하는 59번 문제를 풀었던 방식을 그대로 사용하였다.
59번 문제에서처럼 왼쪽 자식을 들어가기 전에 현재 자신의 수가 들어간다는 의미로 ch[L]에 1을 대입하였다.
오른쪽 자식을 들어갈 때는 현재 자신의 수가 안들어간다는 의미로 ch[L]에 0을 대입하였다.
선택된 친구들의 합과 선택되지 못한 친구들의 합을 따로 구하여 각각을 sum1, sum2에 더해주었다.
그래서 ch[L]의 값이 1인 친구들은 집합에 포함된 숫자이므로 이 친구들은 sum1에 더해주었다.
선생님의 코드와 비교해보면 일을 하나 더 한 셈이다.
정해져있는 수의 합은 항상 같으니 total 값에서 sum1만 빼주면 더 간단한 풀 수 있었다.
ch배열을 사용하여서 1인지 0인지 따로 확인해줄 필요없이 그 원소가 들어갈 때는 sum에 아예 더해버리면 되었다.