[BOJ 1208] 부분수열의 합2 (Java)

BOJ 1208 부분수열의 합2

문제풀이

일단 부분수열의 정의를 잘못알고 있어서 시간이 좀 걸렸다.

• 부분수열은 원래 수열의 일부 항을 원래 순서대로 나열한 것이다. 따라서 순서만 지킨다면 원래 수열에서 연속적으로 가져오지 않아도 된다.(나는 연속된 항만 가져와야한다고 생각했다...)

BOJ 1182 부분수열의 합1 문제의 경우에 시간이 충분했다. 재귀함수를 만들어서 모든 부분수열의 경우를 확인하면 문제가 해결된다. 하지만 이 문제의 경우에는 시간제한이 짧기 때문에 같은 방법으로 풀이할 경우 시간초과를 경험하게 된다. 따라서 다음과 같은 아이디어를 추가로 사용해야한다.

• 모든 합(부분수열)의 경우를 한번에 구하는 것은 오래걸리므로 반으로 나눠 구한다.
  1. 원래 수열을 반으로 나누어 각 1 ~ N/2, N/2 ~ N 의 인덱스 안의 원소로 만들수 있는 모든 합의 경우를 각 리스트에 오름차순으로 저장한다.
  2. 첫 번째 리스트는 0, 두 번째 리스트는 size() - 1 의 인덱스에서 시작한다.
  3. 인덱스를 조절하며 합이 S와 일치하는 경우를 구한다.
     • 두 리스트의 현재 인덱스 원소의 합이 S보다 큰 경우 오른쪽 인덱스 감소
       • 두 리스트의 현재 인덱스 원소의 합이 S보다 작은 경우 왼쪽 인덱스 증가
       • 두 리스트의 현재 인덱스 원소의 합이 S와 같은 경우 ans를 증가시킨다.
• 각 리스트에는 중복값이 들어갈 수 있다. 따라서 해당 경우를 처리해야한다.
• 최악의 경우 각 리스트의 인덱스 그리고 ans는 int의 범위를 넘는다.

구현코드

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

public class Main {
	
	static ArrayList<Integer> A, B;
	static int[] input;
	static int N, S;
	static long ans;
	
	public static void main(String[] args) throws IOException {

		// 데이터 입력받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		S = stoi(st.nextToken());
		
		input = new int[N];
		A = new ArrayList<>();
		B = new ArrayList<>();
		ans = 0;

		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; ++i) {
			input[i] = stoi(st.nextToken());
		}
		
		// 반으로 나눠서 합 구하기 
		makeSumArray(0, 0, N / 2, A);
		makeSumArray(0, N / 2, N, B);
		
		// 양쪽 리스트를 오름차순으로 정렬 
		Collections.sort(A);
		Collections.sort(B);
		
		// 처리
		int left = 0;
		int right = B.size() - 1;
		
		while(left < A.size() && right >= 0) {
			int lValue = A.get(left);
			int rValue = B.get(right);
			
			if(lValue + rValue == S) {
				// 같은 합이 들어있을 수 있기 때문에 다음과 같은 체크를 해줘야한다.
				// left를 증가시키며 lcnt를 증가시킨다.
				long lcnt = 0;
				while(left < A.size() && A.get(left) == lValue) {
					left++;
					lcnt++;
				}
				
				// right를 감소시키며 rcnt를 증가시킨다. 
				long rcnt = 0;
				while(right >= 0 && B.get(right) == rValue) {
					right--;
					rcnt++;
				}
				// 두 경우를 곱하면 모든 경우가 나온다. 
				ans += lcnt * rcnt;
			}
			
			if(lValue + rValue > S) {
				right--;
			}
			
			if(lValue + rValue < S) {
				left++;
			}
		}
		
		// S가 0일때는 아무것도 선택 안했을 경우를 빼줘야한다. 
		ans = S == 0 ? ans - 1 : ans;
		System.out.println(ans);
	}
	
	// 배열안의 요소들로 만들수 있는 모든 합의 경우 
	private static void makeSumArray(int sum, int idx, int end, ArrayList<Integer> list) {
		if(idx == end) {
			list.add(sum);
			return;
		}
		// 현재 idx 선택 
		makeSumArray(sum + input[idx], idx + 1, end, list);
		// 현재 idx 선택 안함 
		makeSumArray(sum, idx + 1, end, list);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}