백준 1208 (부분수열의 합2)

문제

---

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 

 

풀이

---

이 문제도 두개의 포인터를 가지고 푸는 문제다.

 

배열의 중간을 기준으로 부분수열을 구한 뒤  두개의 합을 두개의 포인터를 가지고 합이 S 가 되는 것의 개수를 찾아주면 된다.

 

밑의 코드를 통해 반을 기준으로 부분수열을 구한다.

dfs(0, 0, sumList1, (n / 2));
dfs(0, (n / 2), sumList2, n);

static void dfs(long sum, int idx, List<Long> sumList, int size) {
		
	if(idx == size) {
		sumList.add(sum);
		return;
	}
	
    // 해당 값을 포함
	dfs(sum + list[idx], idx + 1, sumList, size);
    // 해당 값을 포함하지 않음
	dfs(sum, idx + 1, sumList, size);
}

 

이렇게 만들어진 합을 오름차순으로 정렬한 뒤,

int left = 0, right = sumList2.size() - 1;
while(left < sumList1.size() && right >= 0) {
	long leftSum = sumList1.get(left);
	long rightSum = sumList2.get(right);
			
	if(leftSum + rightSum == s) {
		long leftCount = 0;
		long rightCount = 0;
				
		while(left < sumList1.size() && leftSum == sumList1.get(left)) {
			leftCount++;
			left++;
		}
				
		while(right >= 0 && rightSum == sumList2.get(right)) {
			rightCount++;
			right--;
		}
				
		answer += leftCount * rightCount;
	}
			
	else if(leftSum + rightSum < s) {
			left++;
	}
		
	else {
			right--;
	}
}

위 코드와 같이 두개의 포인터로 나누어 합을 구해 S 와 같은지를 확인한 뒤 같다면 같은 값의 갯수를 찾아 곱을하여 경우의 수를 모두 더해주면 된다.

 

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static int n, s;
	static int[] list;
	static long answer = 0;
	static List<Long> sumList1, sumList2;
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		s = Integer.parseInt(st.nextToken());
		
		list = new int[n];
		st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		
		sumList1 = new ArrayList<Long>();
		sumList2 = new ArrayList<Long>();
		
		dfs(0, 0, sumList1, (n / 2));
		dfs(0, (n / 2), sumList2, n);
		
		Collections.sort(sumList1);
		Collections.sort(sumList2);
		
		int left = 0, right = sumList2.size() - 1;
		while(left < sumList1.size() && right >= 0) {
			long leftSum = sumList1.get(left);
			long rightSum = sumList2.get(right);
			
			if(leftSum + rightSum == s) {
				long leftCount = 0;
				long rightCount = 0;
				
				while(left < sumList1.size() && leftSum == sumList1.get(left)) {
					leftCount++;
					left++;
				}
				
				while(right >= 0 && rightSum == sumList2.get(right)) {
					rightCount++;
					right--;
				}
				
				answer += leftCount * rightCount;
			}
			
			else if(leftSum + rightSum < s) {
				left++;
			}
			
			else {
				right--;
			}
		}
		
		if( s == 0 ) {
			answer--;
		}
		
		System.out.println(answer);
	}
	
	static void dfs(long sum, int idx, List<Long> sumList, int size) {
		
		if(idx == size) {
			sumList.add(sum);
			return;
		}
		
		dfs(sum + list[idx], idx + 1, sumList, size);
		dfs(sum, idx + 1, sumList, size);
	}
	
}