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

문제 설명

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

문제 풀이

• 투 포인터 알고리즘으로 풀이하였다.
• 문제에서 배열 길이가 40이라 부분 수열의 갯수는 2^40으로 정수의 범위를 초과한다.
• 따라서, 배열을 2개의 배열로 나누어 각 배열에 대해 부분 수열을 모두 구하고
  2개의 집합에 대해 투포인터 알고리즘을 사용하여 합이 S인 경우의 수를 카운트해준다.

소스 코드 (JAVA)

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, S;
    public static int[] arr = new int[40];
    public static List<Integer> A = new ArrayList<>();
    public static List<Integer> B = new ArrayList<>();


    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        int mid = N/2;
        //반을 나눈 배열의 모든 부분 수열합 구하기
        for (int i = 0; i < (1 << mid); i++) {
            int sum = 0;
            for (int j = 0; j < mid; j++) {
                if ((i & (1<<j)) == (1<<j))
                    sum += arr[j];
            }
            A.add(sum);
        }
        //나머지 반 배열의 모든 부분 수열합 구하기
        for (int i = 0; i < (1 << N-mid); i++) {
            int sum = 0;
            for (int j = 0; j < N-mid; j++) {
                if ((i & (1<<j)) == (1<<j))
                    sum += arr[j + mid];
            }
            B.add(sum);
        }
        Collections.sort(A);
        Collections.sort(B);
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        //투 포인터 알고리즘
        long result = 0;
        int ap = 0, bp = B.size()-1;
        while(ap < A.size() && bp >= 0) {
            int sum = A.get(ap) + B.get(bp);
            if (sum == S) {
                int a = A.get(ap);
                int b = B.get(bp);
                long aCnt = 0, bCnt = 0;
                while(ap < A.size() && A.get(ap) == a) {
                    ap++;
                    aCnt++;
                }
                while(bp >= 0 && B.get(bp) == b) {
                    bp--;
                    bCnt++;
                }
                result += aCnt * bCnt;
            }
            else if (sum > S)
                bp--;
            else if (sum < S)
                ap++;
        }
        if (S == 0) result--;
        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}