백준 | 1182 부분수열의 합 [Java]

💡 Java 11

🔗 문제

---

1182 부분수열의 합 [Link]

💻 코드

---

• 트리 구조로 문제를 생각해본다.

• dfs 를 이용한다.

• 전위 순회를 이용한다.

• 입력값이 1, 2, -3 일 경우를 예로 들어보았다.

• 리프 노드가 각 결과 값이 된다.

• 전위 순회의 순서대로 루트 노드 - 왼쪽 노드 - 오른쪽 노드 순서로 보면 된다.

  • 왼쪽 노드: dfs(depth + 1, sum + numbers[depth])
  • 오른쪽 노드: dfs(depth + 1, sum)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    private static int N;
    private static int S;
    private static int answer = 0;
    private static int[] numbers;

    public static void main(String[] args) throws IOException {
        input();

        dfs(0, 0);

        output();
    }
	
    // 입력 값을 받는 메서드
    private static void input() 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());

        numbers = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
    }

    private static void dfs(int depth, int sum) {
        // 리프 노드이면 최종 값이 S와 같은지 확인함
        if (depth == N) {
            checkSum(sum);
            return;
        }

        dfs(depth + 1, sum + numbers[depth]);
        dfs(depth + 1, sum);
    }

    private static void checkSum(int sum) {
        if (sum == S) {
            answer++;
        }
    }
	
    // 값을 출력하는 메서드
    private static void output() {
        // S가 0 인 경우 초기 sum 값인 0 일 경우를 고려해 1을 빼준다.
        if (S == 0) {
            answer--;
        }

        System.out.println(answer);
    }
}