[백준] 1182번 자바 부분수열의 합

문제 출처 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

 

접근 방식 및 풀이

- 투포인트 알고리즘, DFS 활용 하여 해결 할 수 있다. 

- DFS 알고리즘을 적용하여  지금 위치의 원소를 선택하거, 선택하지 않거나 2가지 조건을 재귀함수로 계속 호출하였다.

 

 

 

소스 코드 

import java.util.Scanner;
 
public class Main {
    static int N, S, count=0;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N= sc.nextInt();
        S= sc.nextInt();
        arr = new int[N];
        for (int i = 0; i <N ; i++) {
            arr[i] =  sc.nextInt();
        }
 
        dfs(0,0);
 
        if(S==0){// count 합이 0인 경우 공집합도 포함되므로 그 수를 하나 빼주고 출력
            count--;
            System.out.println(count);
        }else {
            System.out.println(count);
        }
 
 
    }
 
    private static void dfs(int v , int su){
        if(v==N){// dfs로 돌며 누적시키다가 위치를 나타내는 v이 마지막 위치로 오면 원하는 값인지 아닌지 체크하여 count
            if(su == S){
                count++;
            }
            return;
        }
        // 부분수열, 지금 위치의 원소를 선택하거, 선택하지 않거나
        dfs(v+1, su+arr[v]); // 지금 위치의 원소를 선택
        dfs(v+1, su); // 선택하지 않음.
    }
}

 

 

결과