문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때

두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

코드

public class EqualInSum {
    static int input1;
    static int sum;
    static int total;
    static boolean flag = false;
    static String answer = "NO";

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        input1 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
            total += arr[i];
        }
        dfs(0, arr[0], arr);
        System.out.println(answer);
    }
    public static void dfs(int level, int sum, int[] arr){
        if(flag) return;
        if(level == input1){
            if((total-sum)==sum){
                answer = "YES";
                flag = true;
            }
        }else{
            dfs(level+1, sum+arr[level], arr);
            dfs(level+1, sum, arr);
        }
    }
}

설명

아직 dfs로 문제를 많이 풀어보지 않아서 익숙하지가 않아 직접 풀어보지 못하고 강의 코드를 그대로 옮겼다. 강의 코드를 보면서 내가 느낀점을 간단하게 설명해놓으려고 한다.

우선 dfs로 재귀할때 재귀할 횟수를 정해줄 수를 정해야한다. 여기서는 input1이 배열의 크기이기도 하지만 입력된 숫자의 크기이므로 재귀의 크기이기도하다.

그리고 재귀할 횟수에 도달했을 때 문제에 맞게 풀어낼 로직이다. 우리는 배열의 합이 나머지 배열의 합과 같은지 확인하는 문제였으므로 전체 값에서 합의 값을 뺀 값이 동일한지 확인했다.

마지막으로 dfs를 반복시키는 코드 작성이다. dfs 파라미터로 level값에 +1을 하여 계속 반복하여 값을 넣어주고 sum에는 배열에 값을 더할때와 더하지 않을 때를 나누어 이전에 이진 트리 구조에서 값을 더할지 더하지 않을지 선택하는 것을 이렇게 간단하게 구현할 수 있다.

나는 이진트리의 구조를 만드는 방법을 도저히 머리로 떠올리지 못하여서 풀지 못했는데 dfs로 간단하게 만들어낼 수 있는걸 보고 놀랐다... 물론 아직 많이 풀어보지 않아서 이렇게 모든 문제를 풀수 없겠지만 그래도 점점 감이 잡혀가는 것 같다. 다음 문제도 내용이 비슷하던데 꼭 직접 풀어봐야겠다!