[백준 알고리즘]1208번 부분수열의 합2

백준 알고리즘

부분수열의 합 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	5710	1086	693	20.798%

문제

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

입력

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

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

이 문제는 이전에 풀어본 부분수열의 합(1182번) 전략으로는 풀이하기 힘들다. N의 개수가 40까지 이르게 되면 2^40은 아주 큰 숫자가 되기때문에 시간초과가 발생하게 되기 때문이다. 때문에 2^20의 시간복잡도를 갖는 두개의 배열을 만들어서 풀이하는 전략을 이용해야한다.

때문에 입력받은 인풋 데이터를 반으로 쪼개 배열을 만든 후, 그 배열에서 발생할수 있는 합의 조건들을 전부 list에 담는다,

public static void makeSum(int sum, int idx, int endIdx, int[] arr, ArrayList<Integer> list) {
        if(idx == endIdx) {
            list.add(sum);
            return;
        }

        makeSum(sum, idx+1, endIdx, arr, list);
        makeSum(sum+arr[idx], idx+1, endIdx, arr, list);
}

모든 합을 만들어내는 재귀함수는 다음과 같이 작성하였으며, 호출 시에는 다음과 같이 사용한다.

makeSum(0, 0, N/2, arr, leftList); // 왼쪽 배열의 합을 모은 리스트
makeSum(0, N/2, N, arr, rightList); // 오른쪽 배열의 합을 모은 리스트

 

이후에는 생성된 리스트를 오름차순으로 정렬후에 아래와 같은 전략을 이용해서 풀이한다.

완성된 코드는 다음과 같다.

package baekjoon.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Question1208 {

    static int N;
    static int S;
    static int[] arr;
    static ArrayList<Integer> leftList = new ArrayList<>();
    static ArrayList<Integer> rightList = new ArrayList<>();
    static int ans = 0;

    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();
        }

        makeSum(0, 0, N/2, arr, leftList); // 왼쪽 배열의 합을 모은 리스트
        makeSum(0, N/2, N, arr, rightList); // 오른쪽 배열의 합을 모은 리스트

        Collections.sort(leftList);
        Collections.sort(rightList);

        int leftIdx = 0;
        int rightIdx = rightList.size() - 1;

        while(leftIdx < leftList.size() && rightIdx >= 0) {

            int lv = leftList.get(leftIdx);
            int rv = rightList.get(rightIdx);

            if(lv+rv == S) {
                int lc = 0;
                while(leftIdx<leftList.size() && leftList.get(leftIdx) == lv) {
                    lc++;
                    leftIdx++;
                }

                int rc = 0;
                while(rightIdx>=0 && rightList.get(rightIdx) == rv) {
                    rc++;
                    rightIdx--;
                }

                ans+=lc*rc;
            }

            if(lv+rv > S) rightIdx--;
            if(lv+rv < S) leftIdx++;

        }

        if(S == 0) ans--; // 합계가 0인걸 찾는경우 맨 초기값이 0이므로 이 경우를 한번 빼주어야 함

        System.out.println(ans);
    }

    public static void makeSum(int sum, int idx, int endIdx, int[] arr, ArrayList<Integer> list) {
        if(idx >= endIdx) {
            list.add(sum);
            return;
        }

        makeSum(sum, idx+1, endIdx, arr, list);
        makeSum(sum+arr[idx], idx+1, endIdx, arr, list);
    }


}