[BOJ] 1208 부분수열의 합 2 Java 풀이
이전에 풀었던 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);
}
}