8-1 합이 같은 부분집합

** 코드

package inflearn_8_dfs_bfs_uses;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
 
public class inflearn8_1 {
    static int n,m,k;
    static int[] arr;
    static int total;
    static StringTokenizer st;
    static StringBuilder sb;
    static Set<Integer> set;
    static boolean[] visited;
    static String min;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        total=0;
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            total+=arr[i];
        }
        set = new HashSet<>();
        min = "NO";
        dfs(0, 0);
        System.out.println(min);
        br.close();
        bw.close();
    }
    static void dfs(int start, int sum) {
        if(sum>(total/2))return;
        if(start>=n) {
            if(total-sum==sum) {
                min = "YES";
            }
            return;
        }
        dfs(start+1, sum+arr[start]);
        dfs(start+1, sum);
    }
}
 

 

한번 틀렸던 문제.

DFS를 통해 index의 레벨을 토대로 가지를 뻗어나갔고, 이를 다른 파라미터인 sum에 추가/현상유지를 진행했다.

이를 토대로 Set에 변수를 저장하여, 해당 값이 다시 나온다면 전역변수로 설정한 min을 "YES"로 설정했다.

 

1. 틀린 이유

- 문제 자체를 잘못 이해했다. 문제의 정답은 같은 값이 나오는 부분집합이 있을 때 "YES", 없을 때 "No"인 것이 아니라     "합이 같은 부분집합이 있다면" Result를 "YES"로 바꾸는 것이다.

- 따라서 중복된 값을 제거하기 위해 Set을 사용한 것도 전혀 무의미했고, 중복값이 나왔을때 "YES"로 설정한거 자체가 틀린 문제풀이였다.

 

2. 얻어 갈 점

- 합이 같은 부분집합이다? 그렇다면 Array 전체 요소의 값을 합한 것을 2로 나눈 값이 존재한다면 그런 부분집합이 존재한다는 생각을 하지 못했는데, 이러한 생각을 할 수 있다는 것을 배웠다.

- DFS의 단점 중 하나는 재귀함수의 특성상 정답을 찾았음에도 Stack Frame에 계속 메소드가 쌓여있다보니 가지치기를 하지 않는다면 불필요한 시간소모가 큰 점이다.

-> 이를 전역변수 boolean flag 를 세워 둔 후 정답을 찾는다면 이를 true로 바꾸고, 만약 flag가 true라면 이미 정답 값이 나온 것이니 모든 함수를 return 시키는 것으로 시간초과를 막을 수 있다는 것을 알 수 있었다.