1208번 : 부분수열의 합 2 [Java]

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

해결 방법

N이 40이기 때문에 2^40 => 시간 초과. 따라서 배열을 두 개로 나누어 생각한다. 범위에 해당하는 모든 부분 수열의 합을 리스트에 저장한 뒤, 투 포인터 알고리즘을 사용해 더한 값이 S가 되는 경우를 찾는다.

 

투 포인터 알고리즘

배열에서 두 원소의 합이 어떠한 값과 일치하는 경우의 수를 구할 때 사용되는 알고리즘

다른 방향으로 진행되는 투 포인터 알고리즘의 경우, 배열이 정렬이 되어있어야 한다.

1-1. 배열 a를 이동하는 포인터 준비 -> 왼쪽부터 시작 : 0

1-2 배열 b를 이동하는 포인터 준비 -> 오른쪽부터 시작 : size -1

2. 포인터가 리스트의 범위를 벗어나지 않을때

3. 만약 합이 원하는 값이라면

3-1. 왼쪽 포인터 값과 동일한 값이 오른쪽 요소들 중 얼마나 연속적으로 존재하는지 확인하며 포인터 오른쪽으로 이동

3-2. 오른쪽 포인터 값과 동일한 값이 왼쪽 요소들 중 얼마나 연속적으로 존재하는지 확인하며 포인터 왼쪽으로 이동

3-3. 이동한만큼의 카운트 증가

4. 만약 합이 원하는 값보다 작다면 왼쪽 포인터를 오른쪽으로 한 칸 이동

5. 만약 합이 원하는 값보다 크다면 오른쪽 포인터를 왼쪽으로 한 칸 이동

 

주의할 점

두 리스트에는 공집합이 포함되어 있기 때문에 투 포인터를 통해 합이 0이 나올 수 있다. 이 경우는 정답에서 제외해야 한다.

 

전체 코드

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

public class Main {

	static int N, S;
	static long[] arr;
	static List<Long> left = new ArrayList<>();
	static List<Long> right = new ArrayList<>();

	public static void main(String[] args) throws Exception {

		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		arr = new long[N];

		st = new StringTokenizer(input.readLine(), " ");

		for (int i = 0; i < N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}

		solve(0, N / 2, 0, left);
		solve(N / 2, N, 0, right);

		Collections.sort(left);
		Collections.sort(right);

		long ans = getCnt();

		if (S == 0)
			ans--;

		System.out.println(ans);
	}

	public static void solve(int idx, int end, long sum, List<Long> list) {

		if (idx == end) {
			list.add(sum);
			return;
		}

		solve(idx + 1, end, sum + arr[idx], list);
		solve(idx + 1, end, sum, list);
	}

	public static long getCnt() {

		int pl = 0; 
		int pr = right.size() - 1; 
		long cnt = 0;

		while (pl < left.size() && pr >= 0) {

			long sum = left.get(pl) + right.get(pr);

			if (sum == S) {
				long a = left.get(pl);
				long cnt1 = 0;
				while (pl < left.size() && left.get(pl) == a) {
					pl++;
					cnt1++;
				}

				long b = right.get(pr);
				long cnt2 = 0;
				while (pr >= 0 && right.get(pr) == b) {
					pr--;
					cnt2++;
				}

				cnt += cnt1 * cnt2;
			}

			else if (sum < S)
				pl++;
			else
				pr--;
		}

		return cnt;
	}
}