[알고리즘] 백준 1182 부분수열의 합 -백트랙킹, 그리디- 자바

 

 

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

 

백준 알고리즘 분류에서 백트랙킹 한 문제를 풀어봤습니다.  ㅎㅎ

 

수열이 있는데 해당 수열들의 조합의 합이 S가 되는 경우의 수를 찾는 문제입니다. 

 

보통의 백트랙킹 문제와 다르게 DFS()에서 for문이 필요하진 않았습니다.

 

 

풀이는 주석을 달아놨습니다. 

 

[JAVA]

import java.util.Scanner;

class Main {
    static int[] num;
    private static int N; // 정수의 개수
    private static int S; // 정수의 합
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        num = new int[N];
        for (int i = 0; i < N; i++) {
            num[i] = sc.nextInt();
        }
        dfs(0, 0);
        if (S == 0) System.out.println(answer - 1); // S 0일때 처리 
         else  System.out.println(answer);

    }

    private static void dfs(int depth, int sum) {
        if (depth == N) {
            if (sum == S) answer++;
            return;
        }
        dfs(depth + 1, sum + num[depth]); // 1. 해당 인덱스 더함
        dfs(depth + 1, sum); // 2. 해당 인덱스 더하지않음
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!