[백준] 1182번 - 부분수열의 합 (!) (JAVA)

[백준] 1182번 - 부분수열의 합 (JAVA)

---

[접근 방법]

DFS를 이용하는 풀이 이다.

기존 DFS 문제와 달리 반복문 for 문을 사용하지 않는다.

 

// sum : 현재 부분 수열의 합
public static void dfs(int depth, int sum){
	if (depth == N){
    	if (sum == S){정답 추가}

        return;
	}
    dfs(depth + 1, sum); // 다음 원소를 더하지 않는 경우
    dfs(depth + 1, sum + arr[depth]); // 다음 원소를 더하는 경우

    return;
}

 

 <입력값>

4 0

-7 -3 -2 5

 

위와 같은 트리 구조로 시각화 할 수 있다.

부모노드의 왼쪽 자식 노드는 dfs(depth + 1, sum +arr[depth]) 를 실행 시킨 것으로, 현재 depth가 가리키는 원소를 더한 것이고, 오른쪽 자식 노드는 dfs(depth + 1, sum) 을 실행 시킨 것으로, 원소를 더하지 않고 현재 sum을 그대로 유지시킨 것이다.

 

출력값은 "1" 이 나와야 한다.

그러나 S = 0을 만족하는 부분 집합은 2개이다.

{-3, -2, 5} , {}

원소의 개수가 적어도 한개 존재해야 하므로 공집합인 "{}"은 경우의 수에서 제외해야 한다.

 

따라서 출력값에 S == 0인 경우 -1을 해줘야 하고, 그 외의 경우는 그대로 출력하면 된다.

---

[JAVA 코드]

// 1182번 - 부분수열의 합
import java.util.*;
import java.io.*;

public class Main {

    static int N, S;
    static int[] arr;
    static int answer; // 만족하는 부분수열의 개수

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        answer = 0;
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 1. dfs 실행
        dfs(0, 0);

        // 2. 경우의 수 출력
        // dfs(0, 0) -> dfs(1, 0) -> dfs(2, 0) -> ... -> dfs(N, 0) 인 경우 1가지 제외
        if (S == 0) {bw.write(answer -1 + "\n");}
        else {bw.write(answer+"\n");}

        bw.flush();
        bw.close();
        br.close();

    }

    // sum : 현재 부분 수열의 합
    public static void dfs(int depth, int sum){
        if (depth == N){
            if (sum == S){answer ++;}

            return;
        }
        dfs(depth + 1, sum); // 다음 원소를 더하지 않는 경우
        dfs(depth + 1, sum + arr[depth]); // 다음 원소를 더하는 경우

        return;
    }
}

---

[Rewind]

1. 어려웠던 점

- 이러한 풀이방법을 떠올리지 못하였다.

 

2. 알게된 점

- for문을 사용하지 않고 재귀만으로 사용하는 dfs도 있다는 것을 알게되었다.

 

3. 개선 방향

- 응용 문제를 반복하여 풀어서 숙달해야 함.

 

 

---

[비트 마스크 활용 풀이]

// 1182번 - 부분수열의 합
// 비트마스크 활용
import java.util.*;
import java.io.*;

public class Main {

    static int N, S;
    static int[] arr;
    static int answer; // 만족하는 부분수열의 개수

    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        arr = new int[N];
        answer = 0;
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int sum = 0;
        // 1<<N = 부분 집합의 개수
        for(int i=1; i<(1<<N); i++){
            sum = 0;
            for(int j=0; j<N; j++){
                if((i & (1<<j)) != 0){
                    sum += arr[j]; // 부분집합의 합
                }
            }
            if (sum == S) answer ++;
        }

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();

    }

}