[PS] 인프런 강의 - DFS 1. 합이 같은 부분집합(아마존 인터뷰)

 

문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

 

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있습니다.

 

▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어집니다. 각 원소는 중복되지 않습니다.

 

▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력

 

▣ 입력예제 1
6
1 3 5 6 7 10

 

▣ 출력예제 1
YES

풀이

전에 풀었던 부분집합 문제의 응용버전이다. 그새 까먹었는지 처음에 다른 방법으로 풀려고 했다..

 

집합의 원소를 int 배열을 선언해서 넣어두고, i번째 원소를 사용하는경우 누적합을 더해 왼쪽 자식으로, 사용하지 않는 경우는 오른쪽 자식으로 재귀 호출한다.

 

포인트는 두 부분집합의 합이 서로 같아야 하는데, 서로소인 두 부분집합을 합하면 원래 집합이 되어야 하므로, 두 부분집합의 합은 집합의 총합 1/2이 될 수 밖에 없다는 것이다.

 

따라서 집합의 총합의 1/2 보다 커지면 DFS 트리를 더 뻗을 필요가 없다. DFS 함수에서 이것을 초기에 체크하면 된다.

 

마지막 원소까지 체크했으면 (i = n) 총합 - 누적합 = 누적합 인지를 확인하면 된다 ~

 

코드

import java.util.Scanner;

public class Main {

    static String answer = "NO";
    static int[] arr;
    static int n, total = 0;
    static boolean flag = false; //탈출용

    public static void DFS(int i, int sum) {
        if(flag || sum > total/2) return; //총합의 반보다 커지면 확인해볼 필요X

        //마지막 원소까지 체크했으면
        if(i == n) {
            if((total - sum) == sum) {
                answer = "YES";
                flag = true;
            }
        }
        else {
            DFS(i+1, sum + arr[i]);//left: i를 사용 -> 합계 더한다
            DFS(i+1, sum); //right: i를 사용X -> 합계 더하지 X
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); //1~10
        arr = new int[n];

        //n개의 원소로 구성된 자연수 집합, 중복X
        for(int i=1; i<n; i++) {
            arr[i] = in.nextInt();
            total += arr[i];
        }

        DFS(0, 0); //arr인덱스 0, 합계 0 부터

        System.out.print(answer);
    }
}