[백준 1208] 부분수열의 합2 자바// le_effot//

비슷한 유형의 문제들이 많은데 이 문제는 고생해서 풀었다.

일단 N이 40이니 2^40 이면 1초 안에 들어오지 못하니

 

2^20으로 두번 한다는 발상 조차 떠올리지 못해 다른 블로그들의 도움을 받았다

 

배열을 반으로 쪼개서 (left와 right로 나누겠다)

각각 left와 right에 들어 갈 수 있는 부분수열들을 집어 넣으면 되는데

재귀호출을 이용한다

 

public static void dfs(int level, int end, int sum ,ArrayList<Integer>list) {
        if(level == end) {
            list.add(sum);
            return ;
        }
        dfs(level+1,end,sum+arr[level],list);
        dfs(level+1,end,sum,list);
    }

left의 경우 level은 0부터 시작하며 end는 n/2 이다  (left의 범위는 0~n/2)  

right의 경우 level은 n/2부터 시작하며 end는 n이다 (right의 범위는 n/2~n)

6번째 줄의 경우 지금 단계의 배열값을 더하는 것

7번줄의 경우 지금 단계의 배열값을 더하지 않고 인덱스만 (level) 증가 시키는것

 

결국 이렇게 하면 정해진 모든 범위의 값을 구할 수 있다.

ex) arr[1] = 1, arr[2] =2, arr[3] = 3

6번째 줄은 level=1 , sum=arr[1]  point 1

7번째 줄은 level =1 sum  =0      point 2

 

point 1 에서 호출된 함수가 실행 되면 level = 2 ,sum = arr[1] 

6번째 줄 실행하고 호출된 함수의 결과는 level=3 sum = arr[1]+arr[2]

7번째 줄 실행하고 호출된 함수의 결과는 level=3 sum = arr[1]    (arr[2]를 안더해주고 넘어감)

 

point 2에서 호출된 함수가 실행되면 level=2 , sum=0

6번째 줄 실행하고 호출된 함수의 결과는 level=2 sum = arr[2]

7번째 줄 실행하고 호출된 함수의 결과는 level=2 sum= 0

 

이런식으로 반복되면 결국 모든 값이 다 나오는데 7번째줄 코드 즉 아무것도 더하지 않고 level만 올라가는 것도

결과에 포함됨으로 공집합인 0 의 값 또한 리스트에 들어 갈 수 있다 그러므로 문제서 주어진 s가 0 이면 따로 1개를 빼줘야 한다.

 

그 후 left와 right에 들어 갈 수 있는 합들을 다 담은 다음 투포인터 알고리즘을 이용해서 진행 하면 되는데

두개의 리스트 다 오름차순 정렬을 한 다음

left는 0부터     right는 right.size()-1 부터 투포인터를 진행하면 된다

 

전체 코드

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,s;
    static long cnt=0;
    static int arr[];
    static ArrayList<Integer> left = new ArrayList<>();
    static ArrayList<Integer> right = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        s = Integer.parseInt(t[1]);
        arr = new int[n];
        
        String[] input = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(input[i]);
        }
        dfs(0,n/2,0,left);
        dfs(n/2,n,0,right);
        Collections.sort(left);
        Collections.sort(right);
 
        int left_idx =0;
        int right_idx = right.size()-1;
        
        
        while(left_idx<left.size() && right_idx>=0) {
            int left_sum = left.get(left_idx);
            int right_sum = right.get(right_idx);
            long left_cnt =0;
            long right_cnt = 0;
            if(left_sum+right_sum == s) {
                while(left_idx<left.size() && left.get(left_idx)==left_sum) {
                    left_idx++;
                    left_cnt++;
                }
                while(right_idx>=0 && right.get(right_idx)==right_sum) {
                    right_cnt++;
                    right_idx--;
                }
                cnt+=left_cnt*right_cnt;
                
            }
            else if(left_sum+right_sum>s) {
                right_idx--;
            }
            else if(left_sum+right_sum<s) {
                left_idx++;
            }
        }
        if(s==0) {
            cnt-=1;
        }
        System.out.println(cnt);
    }
    public static void dfs(int level, int end, int sum ,ArrayList<Integer>list) {
        if(level == end) {
            list.add(sum);
            return ;
        }
        dfs(level+1,end,sum+arr[level],list);
        dfs(level+1,end,sum,list);
    }
}