[BOJ] 1208 부분수열의 합 2 Java 풀이

 

 

BOJ 1208번 부분수열의 합2

 

이전에 풀었던 1182번 부분수열의 합 문제와 유사한데, 이번엔 수열 길이의 범위가 40으로 늘어났다. 이전처럼 백트래킹으로 구현하면 주어진 시간 내에 해결할 수가 없다.(2^40 = 약 1조)
* 1182번 부분수열의 합: sdesigner.tistory.com/57

결국 다른 방법을 모색해야 하는데, 나는 여기서 해결방법이 떠오르지 않아 결국 다른 분들의 해결방안을 참고했다. 
* 참고: https://kohen.tistory.com/19

이 문제 풀이의 핵심은 전체 수열을 절반으로 쪼개보는 것이다.

1) 길이가 40으로 수열이 주어지면 길이가 각 20인 수열로 쪼개고, 자른 두 수열을 가지고 부분수열의 합 케이스들을 각각 구한다.

// in main function
// 입력받은 배열을 두 부분으로 나눠 각 부분에서 모든 부분 수열의 합 case들을 list에 저장  
makeSum(0, 0, N/2, leftList);
makeSum(0, N/2, N, rightList);

private static void makeSum(int sum, int start, int end, ArrayList<Integer> list) {
	// 지정된 범위까지 재귀 호출이 끝나는 시점에 list에 넣어 모든 부분수열 합의 경우를 list에 담음  
	if(start == end) {
		list.add(sum);
		return;
	}
	makeSum(sum, start+1, end, list);
	makeSum(sum+arr[start], start+1, end, list);
}

2) 그리고는,  그 두 개의 부분수열의 합 케이스들을 담고 있는 리스트를 오름차순으로 정렬한다.

3) 그 다음에는 하나는 앞에서, 하나는 뒤에서부터 시작해 각 값을 더해보고 S와 비교해본다.

4) 만약 S보다 합이 작다면 앞에서부터 시작한 리스트의 포인터를 1 증가시키고, 만약 S보다 합이 크다면 뒤에서부터 시작한 리스트의 포인터를 1 감소시킨다. 만약 S와 합이 일치하다면 합을 이루는 값들이 각 리스트에 들어있는 개수를 세어 그 쌍을 이룰 수 있는 경우의 수를 세고, 정답으로 출력할 cnt를 그 수만큼 증가시킨다.

++ 부분 수열의 합 케이스들을 구해 리스트에 담을 때, 문제에서 크기가 양수인 부분수열로 조건을 걸었다. 부분합 리스트에 각각 0이 하나씩 반드시 포함되므로, 만약 S가 0인 경우 두 부분 수열에서 모두 하나도 선택하지 않는 경우가 하나 더해지므로, -1을 처리해 출력한다. 

 

전체 코드

package exhaustiveSearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class P1208 {
	static int N, S;
	static long cnt;
	static ArrayList<Integer> leftList = new ArrayList<>();
	static ArrayList<Integer> rightList = new ArrayList<>();
	static int[] arr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 입력받은 배열을 두 부분으로 나눠 각 부분에서 모든 부분 수열의 합 case들을 list에 저장  
		makeSum(0, 0, N/2, leftList);
		makeSum(0, N/2, N, rightList);
		
		// 모든 부분 수열의 합 case가 담긴 list를 오름차순으로 정렬
		Collections.sort(leftList);
		Collections.sort(rightList);

		
		cnt = 0;
		calcC();
		
		// 합이 0인 수를 찾는 경우, 부분 수열의 합을 찾을 때 하나도 선택하지 않은 경우가 포함되기 때문에 한 번 빼주어야 함
		if(S == 0) {
			System.out.println(cnt - 1);
		}else {
			System.out.println(cnt);
		}
		
		
	}// end of main
	
	private static void calcC() {
		int pointerL = 0;
		int pointerR = rightList.size()-1;
		
		while(true) {
			if(pointerL == leftList.size() || pointerR < 0) {
				break;
			}
			int lv = leftList.get(pointerL);
			int rv = rightList.get(pointerR);
			
			// 합이 목적 값과 같으면 합을 이루고 있는 각 수가 list 내에 몇개 있는지 센다. 
			if(lv + rv == S) {
				long lc = 0;
				while(pointerL < leftList.size() && leftList.get(pointerL) == lv) {
					lc++;
					pointerL++;
				}
				
				long rc = 0;
				while(0 <= pointerR && rightList.get(pointerR) == rv) {
					rc++;
					pointerR--;
				}
				cnt += lc * rc;
			}
			
			// 목적하는 값보다 더 큰 경우
			if(lv + rv > S) {
				pointerR--;
			}
			
			// 목적하는 값보다 더 작은 경우 
			if(lv + rv < S) {
				pointerL++;
			}
			
			
		}
		
	}
	
	private static void makeSum(int sum, int start, int end, ArrayList<Integer> list) {
		// 지정된 범위까지 재귀 호출이 끝나는 시점에 list에 넣어 모든 부분수열 합의 경우를 list에 담음  
		if(start == end) {
			list.add(sum);
			return;
		}
		makeSum(sum, start+1, end, list);
		makeSum(sum+arr[start], start+1, end, list);
	}

}