[백준 1208] - 부분수열의 합2 (JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

---

[문제 풀이]

백준 부분수열의 합 이라는 문제와 같지만 N제한이 최대 40이다.

백트래킹 방법을 사용하면 2^40 의 방법이 나와서 이 방법으로는 해결할 수 없다.

전체 수열을 절반으로 쪼개어 모든 방법을 구해야 한다. 2^20 + 2^20 = 1048576*2 이므로 모든 경우를 구할 수 있다.

 

• 주어진 N개의 배열을 반으로 쪼개고 그 모든합을 담을 leftList, rightList 를 만든다.
• 모든합을 구할 함수를 하나 구현하여 leftList, rightList에 값을 담고 오름차순 정렬을 해준다.
• 두개의 포인터를 이용하여 부분수열의 합이 S가 되는 모든 경우의 수를 찾는다.
• 양수로 이루어진 부분수열이므로 빈 부분수열의 경우 1을 정답에서 빼준다.

 

---

[소스 코드]

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

public class Main {

	static int n,s;
	static long ans;
	static ArrayList<Integer> leftList = new ArrayList<>();
	static ArrayList<Integer> rightList = new ArrayList<>();
	static int a[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
	
		a = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		makeSum(0,0,n/2,leftList); //왼쪽 모든 합 구하기
		makeSum(0,n/2,n,rightList); //오른쪽 모든 합 구하기
		
		//오름차순 정렬
		Collections.sort(leftList); 
		Collections.sort(rightList);
		
		findAns();
		
		if(s == 0) ans-=1;
		
		System.out.println(ans);
	}
	
	static void findAns() {
		int pointL = 0;
		int pointR = rightList.size()-1;
		while(pointL < leftList.size() && pointR >= 0) {
			int valL = leftList.get(pointL);
			int valR = rightList.get(pointR);
			
			if(valL + valR == s) {
				long cntL = 0;
				long cntR = 0;
				
				//왼쪽리스트에서 같은 수 찾기
				while(pointL < leftList.size() && valL == leftList.get(pointL)) {
					cntL++;
					pointL++;
				}
				//오른쪽리스트에서 같은 수 찾기
				while(pointR >= 0 && valR == rightList.get(pointR)) {
					cntR++;
					pointR--;
				}
				ans += cntL*cntR;
			}
			if(valL + valR < s) { 
				pointL++;
			}
			if(valL + valR > s) {
				pointR--;
			}				
		}
	}
	
	static void makeSum(int sum, int start, int end, ArrayList<Integer> list) {
		if(start == end) {
			list.add(sum);
			return;
		}
		
		makeSum(sum, start+1, end, list);
		makeSum(sum+a[start], start+1, end, list);
	}
}