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

📖 문제

 

 

알고리즘❓ 풀어내기❗️

모든 경우의 수는 각 원소를 뽑는다 / 안 뽑는다로 나뉜다. 따라서 완전탐색을 통해 합이 S가 되는 모든 경우의 수를 탐색하고, 트리구조를 이루기 때문에 DFS 방식으로 풀 수 있다.

예를 들어, 원소 {A, B, C} 라면,
index = 0 일 때는 아무것도 선택하지 않았을 때, 부분수열 = {0} (공집합)
index = 1 일 때는 이전 부분 수열에 A를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {A}, {0}
index = 2 일 때는 이전 부분 수열에 B를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {AB}, {A}, {B}, {0}
index = 3 일 때는 이전 부분 수열에 C를 가졌냐 안 가졌냐로 나뉨. 부분수열 = {ABC}, {AB}, {AC}, {BC}, {A}, {B}, {C}, {0}
이런 식으로 진행이 된다.

 

 

부분집합에 대한 이해가 부족하다면 아래 포스팅을 참고해도 좋겠다.

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 부분집합(Subset)

[알고리즘] 부분집합(Subset)

 

 

🧑🏻‍💻 풀이 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, S, count;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        count = 0;
        dfs(0, 0);

        if (S == 0) {
            System.out.println(count - 1);
        } else {
            System.out.println(count);
        }
    }

    static void dfs(int index, int sum) {
    	// 종료 조건
        if (N == index) {
            if (S == sum) {
                count++;
            }
            return;
        }
		
        // 지금 인덱스 뽑는다.
        dfs(index + 1, sum + arr[index]);
        // 지금 인덱스 안뽑는다.
        dfs(index + 1, sum);
    }
}

▶ if (S == 0) { System.out.println(count - 1) : 모든 원소를 뽑지 않는 경우의 수도 포함이기 때문에 문제에서의 크기가 양수인 부분수열에 위배된다. 따라서 S가 0으로 주어진다면 공집합일 때의 경우의 수를 제외시켜야 하므로 결괏값에서 - 1을 해주어야 한다.