[BOJ 1208] 부분수열의 합 2 (Java)

BOJ 1208 부분수열의 합 2

난이도 : 골드 1

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

1208번: 부분수열의 합 2

 

전략

BOJ 1806 부분합처럼 연속된 부분 수열의 합을 구하는 문제는 누적합과 투포인터를 사용해서 풀 수 있다.

하지만 이 문제는 연속이라는 조건이 없기 때문에 모든 조합을 확인해야 한다.

수열의 크기 N은 최대 40으로 O(2^N)으로는 풀 수 없다.

 

이런 문제는 다항시간으로 줄일 수는 없지만 meet in the middle 전략을 이용하여 조금 더 효율적인 계산을 할 수 있다.

1. N/2 크기의 두 수열로 나눈다. 

2. 각 수열에서 모든 조합을 찾는다.

3. 두 조합 리스트를 합해서 S를 만들 수 있는지 검사한다.

 

두 수열로 나누는 것에서 분할정복과 비슷해보이지만, 분할정복은 항상 subproblem으로 나누어서 나눠지는 크기에 따라 로그 시간복잡도까지 향상 가능하지만 이 문제에서는 계속 나눌 수가 없다.

더 이상 나누면 그 나눈 배열끼리의 조합을 다시 계산해줘야 하기 때문이다.

 

나는 첫번째 수열의 조합은 HashMap에 저장하고 두번째 수열을 순회하면서 합이 S가 되는 경우를 세는 방식으로 풀었다.

이 풀이의 시간복잡도는 O(2^(N/2) * 2)가 되어 최대 40인 N에 대해 충분히 연산 가능해진다.

 

시행착오

분명 정상적으로 돌아가는 것처럼 보이는데 틀렸다고 했다. 그래서 나올 수 있는 가장 높은 결과를 내도록 TC를 만들어보았다.

40 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

어떤 원소를 선택해도 항상 S와 일치하기 때문에 정답은 2^40 - 1 = 1099511627775이다. (모두 선택하지 않는 경우 제외)

하지만 1099510579200이 나와서 잘 생각해보니 두번째 조합을 기준으로 비교하기 때문에 첫번째 조합만으로 S가 일치하는 경우가 고려되지 않은 것이었다.

따라서

1. 첫번째 조합 == S -> += 1

2. 두번째 조합 == S -> += 1

3. += (S - 두번째 조합)이 가리키는 map의 값

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, S;
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        S = Integer.parseInt(line[1]);
        int[] first = new int[N / 2];
        int[] second = new int[N - first.length];
        line = br.readLine().split(" ");

        for (int i=0; i<N; i++) {
            if (i < first.length)
                first[i] = Integer.parseInt(line[i]);
            else
                second[i - first.length] = Integer.parseInt(line[i]);
        }

        ArrayList<Integer> firstComb = getComb(first);
        ArrayList<Integer> secondComb = getComb(second);
        HashMap<Integer, Integer> firstMap = new HashMap();

        long ans = 0;
        for (int num : firstComb) {
            firstMap.merge(num, 1, (a, b) -> (int) a + b);
            if (num == S)
                ans++;
        }

        for (int num : secondComb) {
            if (num == S)
                ans++;
            if (firstMap.containsKey(S - num))
                ans += firstMap.get(S - num);
        }
        System.out.println(ans);
    }

    static ArrayList<Integer> getComb(final int[] arr) {
        ArrayList<Integer> ret = new ArrayList<>();
        Stack<Num> st = new Stack<>();

        if (arr.length > 0)
            st.push(new Num(-1, 0, 0));

        while (!st.isEmpty()) {
            Num cur = st.pop();
            if (cur.idx == arr.length - 1) {
                if (cur.cnt > 0)
                    ret.add(cur.value);
                continue;
            }

            st.push(new Num(cur.idx + 1, cur.cnt + 1, cur.value + arr[cur.idx + 1]));
            st.push(new Num(cur.idx + 1, cur.cnt, cur.value));
        }

        return ret;
    }

    static class Num {
        int idx;
        int value;
        int cnt;
        Num(int idx, int cnt, int value) {
            this.idx = idx;
            this.cnt = cnt;
            this.value = value;
        }
    }
}

 

깨달은 점

브루트포스로 해결하기 힘든 연산횟수일 때는 분할정복까지는 아니어도 이러한 전략으로 시간복잡도를 줄일 수 있구나 생각했다.

예전에 풀었던 BOJ 1799 비숍 문제처럼 나눠서 풀 수 있는 구조가 있는지 생각해보는 것이 좋은 습관이 될 것 같다.