[BOJ] 1182. 부분수열의 합

기본적인 부분수열의 합문제이다. 

두가지 방법으로 풀어보았다. 첫번째로는 비트마스킹을 이용하여 모든 부분수열을 구하는 방식으로 구현하였다.
두번째로는 재귀적인 DFS 방식으로 현재항을 더해주는 경우, 현재항을 더해주지 않는 경우로 나누어 2번씩 호출해주는 방식으로 풀었다. 이때 기저조건으로는 마지막인덱스에 도달하였을 경우 종료시키게 해주었다.

시간은 비트마스킹을 사용하는 첫번째 코드보다 두번째 재귀적인 DFS를 사용한 코드가 빨랐다.

1. 비트마스킹 사용

package chap07;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1182_부분수열의합 {
    static int[] arr;
    static int N,target;
    static int sum,answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =null;
        
        st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        target=Integer.parseInt(st.nextToken());
        
        arr=new int[N];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            arr[i]=Integer.parseInt(st.nextToken());
        }
        func();
        if(target==0)
            System.out.println(answer-1);
        else
            System.out.println(answer);
    }
    
    static void func() {
        
        for(int i=0;i<(1<<N);i++) {
            sum=0;
            for(int j=0;j<=N;j++) {
                if(((1<<j) & i) >0) {
                    sum+=arr[j];
                }
            }
            if(sum==target)
                answer++;
        }
        
    }
}
 

 

2. DFS사용

package chap07;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1182_부분수열의합_re {
    static int[] arr;
    static int N,target;
    static int sum,answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st =null;
        
        st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        target=Integer.parseInt(st.nextToken());
        
        arr=new int[N];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            arr[i]=Integer.parseInt(st.nextToken());
        }
        func(0,0);
        if(target==0)
            System.out.println(answer-1);
        else
            System.out.println(answer);
    }
    
    static void func(int sum, int depth) {
        if(depth==N) {
            if(sum==target)
                answer++;
            return;
        }
        
        func(sum+arr[depth],depth+1);        //더해주는 경우
        func(sum,depth+1);                    //더해주지 않는 경우
    }
}