[DFS] 1. 합이 같은 부분집합

<<풀이>>

 

-나의 풀이-

 

우선 나의 풀이는 틀렸따 ㅋㅋㅋ 나름 잘 했다고 생각했지만, 시도는 좋았다고 생각한다. 어떤 부분에서 문제가 있을 거 같은데, 시간 상 아직 체크를 하지 못했다. 

import java.util.Scanner;

class Main{
    private static int[] arr;
    private static int[] ch;
    private static int sum;
    private static int target;
    private String DFS(int v) {
        sum += v;
        for (int x : arr) {
            if (ch[x] != 1) {
                target += x;
            }
        }
        if (sum == target) return "YES";
        else {
            target = 0;
            for (int x : arr) {
                if (ch[x] != 1) {
                    ch[x] = 1;
                    DFS(x);
                    sum -= x;
                    ch[x] = 0;
                }
            }
        }
        return "NO";
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        arr = new int[n];
        ch = new int[11];

        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        ch[arr[0]] = 1;
        System.out.println(T.DFS(arr[0]));
    }
}

 

 

-강사님 풀이-

 

크 ~ 이 문제도 기가막히게 푸셨다. 나도 이런 풀이는 알고는 있었지만, 떠오르지 못했다.. ㅠ

일단 전체적인 맥락은 사용하거나 사용 안 하거나 이렇게 두 가지로 나눠서 진행을 했다.

그리고 return 타입도 void로 해서 진행을 했다.

 

이후, 값이 total 값에 sum을 빼거나 total을 2로 나눴을 때 값이 sum과 같다면 answer에 "YES" 를 출력하게 했다. 

answer가 "YES"가 되는 순간 부터는 더 이상 계산이 필요가 없기 때문에 flag 를 false로 해둔 것을 true로 바꿈으로써 

계속 return이 되도록 하여, 계산을 끝내도록 했다.

 

 

 

import java.util.Scanner;

class Main {
    static String answer = "NO";
    static int n, total = 0;
    boolean flag = false;

    public void DFS(int L, int sum, int[] arr) {
        if (flag) return;
        if (sum > total / 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) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            total += arr[i];
        }
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

 

참 코드가 많이 깔끔해졌다. 어떻게 보면 개념적으로 알고는 있지만 아직 내 것이 아니다보니 제대로 활용은 못한 거 같다.

지금은 이렇지만 점차 늘것이라 생각하고, 내 혼자 다시 코드 작성해서 풀어봐야겠다!