[백준]1208 부분수열의 합2

1208번: 부분수열의 합 2 (acmicpc.net)

1208번: 부분수열의 합 2

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

내풀이 

처음에 그냥 부분 수열을 dfs로 구해서 답을 찾아볼까 했는데 너무나 당연하게 시간 초과가 난다.

왜냐 단순하게 입력이 최대 40개 들어올 수 있는데 40개라 생각하면 

선택할까 말까라는 2가지 선택지를 40번 반복하기에 => 2^40의 경우의 수를 고려하는 것이고 O(2^N)의 알고리즘 이기 때문이다.

 

그래서 검색을 통해 알게된 이 문제를 푸는 방법은 2^40 을 2^20으로 줄이는 것이다.

전체 입력 중 앞 쪽 절반 으로 부분

수열들의 합들을 구하여 리스트로 뽑고, O(2^(N/2))

전체 입력 중 뒤 쪽 절반 으로 부분 수열들의 합들을 구하여 리스트로 뽑고, O(2^(N/2))

이 두 배열을 투포인터 알고리즘으로 원하는 값이 나올 때 세어서 몇번 나오는지 찾으면 답을 찾을 수 있다. O(N)

사소한(?) 투포인터 알고리즘의 수행시간을 제외하고 생각하면

2^40 => 2 * 2^20 = 2^21 으로 줄일 수 있으니 엄청나게 줄일 수 있었다.

 

전체 소스코드

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

public class Main {
    static BufferedReader input;
    static StringBuilder output = new StringBuilder();
    static String src = "40 0\n" +
            "100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000 -100000\n";

    static int N, S;
    static long data[];
    static List<Long> left = new ArrayList<>();
    static List<Long> right = new ArrayList<>();

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

        input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        //풀이
        StringTokenizer str = new StringTokenizer(input.readLine());
        N = Integer.parseInt(str.nextToken());
        S = Integer.parseInt(str.nextToken());

        str = new StringTokenizer(input.readLine());
        data = new long[N];
        for (int i = 0; i < N; i++) {
            data[i] = Long.parseLong(str.nextToken());
        }

        getSubsequence(0,N/2,0,left); // 앞쪽 절반 모든 부분 수열의 합들 구하기
        getSubsequence(N/2,N,0,right); // 뒤쪽 절반 모든 부분 수열의 합들 구하기

        // 둘 다 오름차순으로 정렬
        Collections.sort(left);
        Collections.sort(right);

        //투 포인터 알고리즘으로 답을 구한다
        long cnt = getCnt();

        // 공집합끼리 더해 0이 되는 경우가 답에 섞일 경우 count--
        if(S==0){
            cnt--;
        }

        System.out.println(cnt);
    }

    public static void getSubsequence(int idx, int end, long sum, List<Long> list){
        if (idx == end) {
            list.add(sum);
            return;
        }

        getSubsequence(idx + 1, end, sum + data[idx], list);
        getSubsequence(idx + 1, end, sum, list);
    }

    // 투 포인터 알고리즘으로 0이 되는 경우 구하기
    public static long getCnt() {

        int pl = 0;
        int pr = right.size() - 1;
        long cnt = 0;

        while (pl < left.size() && pr >= 0) {

            long sum = left.get(pl) + right.get(pr);

            if (sum == S) {
                long a = left.get(pl);
                long cnt1 = 0;
                while (pl < left.size() && left.get(pl) == a) {
                    pl++;
                    cnt1++;
                }

                long b = right.get(pr);
                long cnt2 = 0;
                while (pr >= 0 && right.get(pr) == b) {
                    pr--;
                    cnt2++;
                }

                cnt += cnt1 * cnt2;
            }

            else if (sum < S)
                pl++;
            else
                pr--;
        }

        return cnt;
    }

}