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

문제보기

부분수열의 합 1과 다 똑같은데 N범위가 두배로 늘어났다. 따라서 1에서 처럼 모든 경우의 수를 다 찾는(2^N)것은 1조가 넘어가서 힘들다.
그래서 경우를 두개로 쪼개서 풀어준다. 주어진 수열을 반으로 쪼개면 최대 20개씩 쪼개지므로 1에서 처럼 부분 수열의 합을 전수조사해서 클리어할 수 있다. 다만 중간중간 주의해야할 점들이 있다. 자세한것은 주석으로 보자~!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
	
	static int ip(String s) { return Integer.parseInt(s); };
	
	static HashSet<Long> set1; // 첫번째 부분수열을 중복없이 저장할 해쉬셋 
	static HashSet<Long> set2; // 두번째 부분수열을 중복없이 저장할 해쉬셋
	
	static HashMap<Long, Integer> map1; // 키 : 부분수열의 합 , 값 : 그 합이 나오는 경우의 수 
	static HashMap<Long, Integer> map2; 
	
	// 부분수열의 합을 구할 함수 
	// 인자는 순서대로 해당수열 내 인덱스, 여태까지 모은 합, 해당수열의 크기, 해당 수열, 수열의 이름(1 혹은 2), 여태까지 포함한 원소의 갯수
    public static void go(int idx, long sum, int size, int[] arr, int name, int cnt){

        if(idx >= size){ // 모든 원소에 대해 넣기 or 안넣기 경우가 모두 끝났다면 
        	if(cnt > 0) { // 아무것도 안고르는건 안된다(부분수열의 크기가 양수라고 명시되어있음)
        		if(name == 1) { // 1번 배열이라면 

            		if(map1.containsKey(sum)) { // 기존에 해쉬맵에 들어있었다면 
            			map1.put(sum, map1.get(sum)+1); // 갯수 +1
            		}else { // 처음 들어오는거라면 
						set1.add(sum); // set에도 넣고 
            			map1.put(sum, 1); // map에도 새로 추가 
            		}
            	}else {
            		set2.add(sum);
            		if(map2.containsKey(sum)) {
            			map2.put(sum, map2.get(sum)+1);
            		}else {
            			map2.put(sum, 1);
            		}
            	}
        	}
        	
            return;
        }
        
        go(idx+1, sum + arr[idx], size, arr, name, cnt+1); // 해당 인덱스의 수열을 포함해서 진행 
        go(idx+1, sum, size, arr, name, cnt); // 안포함하고 진행 
    }
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = ip(st.nextToken());
		int s = ip(st.nextToken());
		int[] arr = new int[n]; // 전체 수열을 받는다 
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) {
			arr[i] = ip(st.nextToken());
		}
		// 크기를 절반짤라서 두개의 작은 수열로 나눈다 
		int[] sub1 = new int[n/2];
		System.arraycopy(arr, 0, sub1, 0, n/2);
		int[] sub2 = new int[n-n/2];
		System.arraycopy(arr, n/2, sub2, 0, n-n/2);
		
		
		set1 = new HashSet<Long>();
		set2 = new HashSet<Long>();
		map1 = new HashMap<Long, Integer>();
		map2 = new HashMap<Long, Integer>();
		
		// 첫번째 작은 수열부터 출발~
		go(0, 0, n/2, sub1, 1, 0);
		// 두번째 작은 수열 출발
		go(0, 0, n-n/2, sub2, 2, 0);
		
		// 크기순으로 정렬해줘야 하므로 set은 더이상 사용할 수 없다
		ArrayList<Long> sum1 = new ArrayList<Long>(set1);
		ArrayList<Long> sum2 = new ArrayList<Long>(set2);
		// 정렬
		Collections.sort(sum1);
		Collections.sort(sum2);
		
		// 정답을 저장할 변수 
		long ans = 0;

		// 일단 쪼갠 수열 자체적으로 s를 만족시킬 수도 있지 않나? 
		// 있다면 정답에 더해주도록 하자 
		if(map1.containsKey((long)s)){
			ans += map1.get((long)s);
		}
		if(map2.containsKey((long)s)){
			ans += map2.get((long)s);
		}
		
		// 이제 본격적으로 두 작은수열의 조합을 통해 s를 만들 수 있는지 살펴보도록 하자
		// sub1 은 0번째 인덱스부터 시작하고, sub2는 가장 큰 인덱스부터 시작한다 
		int l = 0;
		int r = sum2.size()-1;
		

		while(l < sum1.size() && r >= 0) {

			long add = sum1.get(l) + sum2.get(r); // 두 값의 합
			
			if(add == s) { // 이 우리가 구할 S와 같다면
				
				// 두 값을 만들어낼 수 있는 경우의 수 끼리 곱해서 ans에 더해준다
				// 나는 해쉬맵의 값 부분을 integer로 정의했기 때문에 앞에 형변환을 안붙혀주면 최악의 경우 터질 수 있었다
				ans += (long)map1.get(sum1.get(l)) * (long)map2.get(sum2.get(r));
				// 진행
				l++;
				r--;
			
			}else if( add < s ) {
				l++;
			}else {
				r--;
			}
		}
		
		System.out.println(ans);
		
	}
}