[BOJ_1182] 부분수열의 합

설명

---

처음에 2^20이 엄청나게 큰 수가 될 것으로 판단하여 접근을 쉽사리 못하였는데 모든 수를 탐색하면서 선택하고 안 하고를 반복해도 1048576의 반복문을 도는 것을 확인하여 아래와 같이 접근하였다.

 

그리고, 계속해서 75% 정도에서 틀리길래 sum == 0 인 경우를 생각해보면 모든 부분수열을 탐색하면서 모두 선택하지 않는 공집합의 경우에는 문제에서 요구하는 크기가 양수인 부분집합이 아니므로 선택 대상이 되지 않는다. 그 경우를 제외하기 위해서 if문을 추가하였다.

 

코드

---

package backtracking;

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

public class BOJ_1182 {
    static int N;
    static int arr[];
    static int ans;
    static int S;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());

        S = Integer.parseInt(tk.nextToken());

        arr = new int[N];

        ans = 0;

        tk = new StringTokenizer(in.readLine()," ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(tk.nextToken());
        }

        if(S == 0){
            ans--;
        }

        go(0,0);

        System.out.println(ans);

    }
    private static void go(int idx,int sum) {
        if(idx == N){
            if(sum == S){
                ans++;
                return;
            }
            return;
        }
        go(idx+1,sum);

        go(idx+1,sum + arr[idx]);
    }
}

1182번: 부분수열의 합