BOJ) 부분수열의 합 2

부분수열의 합 2

1208번: 부분수열의 합 2

풀이

오늘 문제가 너무 안풀려서 하나만 더 풀어보자 하고 기출문제와 유사한 문제라고해서 풀어봤다.

오랜만에 백준 문제를 풀어서 그런지 어려웠다.

그리고 백준이 바로 코딩하기에 친절하지가 않아서 처음 구조를 잡아나갈 때를 제외하고는 ide힘을 빌려야했다.. ㅠ

 

N개의 정수로 이루어진 배열에서 부분 수열의 합이 S가 되는 경우의 수를 구하는 문제다.

N은 40 이하의 수, S는 -1,000,000 ~ 1,000,000의 수로 주어진다.

40이면 잘만 컨트롤하면 dfs로 한번에 풀리지 않을까 했는데, 2^40은 통제하기에 너무 컸다..

그래서 열심히 구글링을 한 결과, 거의 모든 분들이 집합을 1~20, 21~40까지 잘라서 왼쪽과 오른쪽의 부분 수열합을 구한 뒤, 투 포인터를 활용해 정답을 찾아냈다. 그러면 2^20 *2로 dfs가 확 줄게되어 할만하다.. 정말 똑똑한 사람들이 많은 것 같다...

 

먼저,  DFS를 통해 0 ~ 2/N , 2/N ~ N에 해당하는 부분수열의 합을 각각 저장한다.

그 다음으로 부분 수열의 합을 오름차순으로 정렬하여, left는 좌측 인덱스부터, right는 우측 인덱스부터 탐색하면서 두 부분 수열 합을 더한 결과가 S가 되는 지점을 찾는다.

이 때, left + right == S인 지점에서, left에 같은 값의 수가 몇 개 있는지, right에는 몇 개가 있는지 세어주어 경우의 수를 구해준다.

 

주의할 점은, S가 0인 경우 공집합이 존재하기 때문에 답에서 -1을 카운트 해줘야한다.

또한, answer와 count의 경우 int로 설정하면 범위를 초과하기 때문에 long 형으로 선언해주어야 한다. (이 부분을 놓치면, 74%에서 실패가 뜸)

 

 

코드

 

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

class Main {
    static ArrayList<Integer> left;
    static ArrayList<Integer> right;

    private static long solution(int S, int[] numArr) {
        left = new ArrayList<>();
        right = new ArrayList<>();

        permutation(0,numArr.length/2, numArr,S,0, left);    // left 부분 수열
        permutation(numArr.length/2,numArr.length, numArr,S,0, right);    // right 부분 수열

        return getAnswer(S);
    }

    private static long getAnswer(int S) {
        long answer =0;

        Collections.sort(left);
        Collections.sort(right);

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

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

            int leftSum = left.get(leftIdx);
            int rightSum = right.get(rightIdx);

            if(leftSum+rightSum == S) { // left + right 가 S일 때
                long leftCnt = 0;
                
                while(leftIdx<left.size() && left.get(leftIdx) == leftSum) {    // leftSum 값이 같은 부분 갯수 세주기
                    leftCnt++;
                    leftIdx++;
                }

                long rightCnt = 0;
               
                while(rightIdx>=0 && right.get(rightIdx) == rightSum) {
                    rightCnt++;
                    rightIdx--;
                }

                answer += leftCnt*rightCnt;
            }

            if(leftSum+rightSum > S) {
                rightIdx--;
            }
            if(leftSum+rightSum < S) {
                leftIdx++;
            }
        }
        if(S ==0) {
            answer--;
        }
        return answer;
    }

    private static void permutation(int idx, int end, int[] numArr, int S, int sum, ArrayList<Integer> list) {
        if(idx >= end) {
            list.add(sum);
            return;
        }

        permutation(idx+1, end, numArr, S, sum+numArr[idx],list);
        permutation(idx+1, end, numArr, S, sum,list);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = br.readLine();
        int N = Integer.parseInt(inputStr.split(" ")[0]);
        int S = Integer.parseInt(inputStr.split(" ")[1]);
        int[] numArr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            numArr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(solution(S,numArr));

        br.close();
    }
}