[알고리즘/java] DFS 활용 / 합이 같은 부분집합

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

 

문제 : 

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

입력 : 첫 번째 줄에 자연수 N(1<=N<=10)이 주어진다.

두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

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

 

입력 예시 :

1 3 5 6 7 10

 

출력 예시 : 

YES

---

부분집합 구하기 문제는 저번 게시글

2021.12.11 - [알고리즘/자바 알고리즘 문제풀이: 코딩테스트 대비] - [알고리즘/java] 부분집합 구하기(DFS)

에서 한 번 했던 적이 있다.

각 원소를 부분집합의 원소로 사용하느냐(O) / 안 하느냐(X) 로 각각 나누어서 DFS를 하는데, 

사용하는 원소들을 출력하기 위해 check 배열을 사용했었다.

 

하지만 이번 문제에서는 주어진 집합의 부분 집합을 구하고 조건을 만족시키느냐 (둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 된다) 만 출력하면 되기 때문에 따로 check 배열은 두지 않는다.

 

 

 

입력 예시인  {1 3 5 6 7 10} 집합의 부분 집합 원소를 구할 때,

만약 {1 3 5를} 한 집합으로 구하면 자연히 나머지 원소들 {6 7 10} 은 또 다른 집합이 되기 때문에 두 가지를 나누어서 구할 필요가 없다.

 

문제에서 만족해야 하는 조건인 "두 부분집합의 원소의 합이 서로 같은 경우"는 결국

원소들을 선택해서 만들어진 부분집합의 합 = 선택하지 않은 원소들의 부분집합의 합 이어야 하므로

 

전체 원소들의 합 - 원소들을 선택해서 만들어진 부분집합의 합 = 원소들을 선택해서 만들어진 부분집합의 합

(total[전체집합] - sum[부분집합] = sum[부분집합])

을 만족시키는 부분집합이 있는지 없는지를 판별하면 된다.

 

 

 

 

---

전체 집합의 원소를

 

{1 3 5 6 7 10} 

 0 1 2 3 4 5 번째 원소들이라고 생각하고 DFS 진행.

 

 

 

 

 

< 전체 코드 >

import java.util.*;

public class Main {

	private static int n, total = 0;
	private static String answer = "NO";
	private static boolean flag = false;

	public static void DFS(int L, int sum, int[] arr) {

		if (flag)
			return;
		if (sum > total / 2) // 부분집합의 합이 전체/2값보다 크다면 고려할 필요없음
			return;

		if (L == n) {
			if ((total - sum) == sum) {
				answer = "YES";
				flag = true;
			}

		} else {
			DFS(L + 1, sum + arr[L], arr); // 해당 원소를 부분집합으로 사용함
			DFS(L + 1, sum, arr); // 해당 원소를 부분집합으로 사용하지 않음.
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();

		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scan.nextInt();
			total += arr[i];
		}

		DFS(0, 0, arr);

		System.out.println(answer);

		scan.close();
	}

}

 

부분집합 하나가 만들어지는 시점인 조건문 (L== n)인 경우에서 조건을 만족시켰을 때 리턴 시키지 않고 flag를 이용하는 이유는 back했을 때 스택프레임에 쌓인 것들을 모두 종료시켜버리기 위함이다.