1208

부분 수열의 합2 : https://www.acmicpc.net/problem/1208

 

문제풀이에 실패함 머릿속으로는 dfs로 밖에 떠오르지 않아 아래의 사이트들을 참조하였다.

그중 첫번째 사이트에서 본 내용을 기반으로 어떻게 풀었는지 정도만 파악하였다.

 

 

부분집합을 구하는 방식을 이해하기 어려웠다. 하나하나 뜯어보고 나서야 조금은 알게 되었다.

부분집합의 개수는 원소 하나당 포함/비포함인 경우의 합이므로 2^N개가 된다.

그것을 이용해 배열을 반으로 나눈다.

( 조건상 N=40까지 가능하므로 2^40은 인자로 사용할 수없다. 그래서 반으로 나누었다고한다)

 

 

아래의 배열은 개수가 하나라도 틀어지면 정답이 나오지 않는다.. 초보자가 흉내낼만한 코드는 아닌것 같다.

 

a = new int[1 << (N - size)+10];
b = new int[1 << (size)];

 

루프에서도 전부 비트 shift 연산을 사용하여 표현한다.

이부분들이 멋지기도 하고, 잘 알아야겠지만 실제 응용에 사용하려면 많은 연습과 주의가 필요하지 않나 하는 생각이든다.

 

직관적인 이해는 두번째 사이트의 내용이 더 수월하다.

 

참조한 사이트:

https://loosie.tistory.com/563

https://kora1492.tistory.com/22

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
5 0
-7 -3 -2 5 8
*/
public class Main {

	static int N, S;
	static int[] arr;
	static int[] a, b;
	static int idx;

	static int answer = 0;
	private static boolean DBG = true;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		int size = N / 2;

		arr = new int[N];

		// ex) 짝수인 경우를 고려하여 배열원소의 개수를 선언 N=5, size=2 , N-size=3
		// N개의 원소의 부분집합의 수, 2^N (공집합 포함)
		// N<=40 조건이 있으므로, MAX는 2^40 int를 초과하므로 반으로 쪼갠다.
		a = new int[1 << (N - size)];
		b = new int[1 << (size)];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 앞부분 부분집합의 개수
		// 원소의 개수 : 비트의 수만큼 체크한다.
		// ex) i=3, 0x0011 j=0x0001 ,j=1 0x0010은 3번째 부분집합의 원소가 0,1번째 arr의 index를 의미
		// 따라서 a[3] = arr[0] + arr[1] 이 된다.
		for (int i = 0; i < (1 << (N - size)); i++) {
			for (int j = 0; j < (N - size); j++) {
				if ((i & (1 << j)) == (1 << j)) {
					a[i] += arr[j];
				}
			}
		}
		for (int i = 0; i < (1 << size); i++) {
			for (int j = 0; j < size; j++) {
				if ((i & (1 << j)) == (1 << j)) {
					b[i] += arr[j + (N - size)];
				}
			}
		}

		if (DBG) {
			// before sort
			System.out.println("before sort");
			System.out.println("a의 부분 집합의 합 배열");
			for (int v : a)
				System.out.print(v + " ");
			System.out.println();

			System.out.println("b의 부분 집합의 합 배열");
			for (int v : b)
				System.out.print(v + " ");
			System.out.println();
			Arrays.sort(a);
			Arrays.sort(b);
			// after sort
			System.out.println("after sort");
			System.out.println("a의 부분 집합의 합 배열");
			for (int v : a)
				System.out.print(v + " ");
			System.out.println();

			System.out.println("b의 부분 집합의 합 배열");
			for (int v : b)
				System.out.print(v + " ");
			System.out.println();
		}
		int lt = 0;
		int rt = b.length - 1;
		long cnt = 0;

		while (lt < a.length && rt > -1) {
			int av = a[lt], bv = b[rt];
			if (a[lt] + b[rt] == S) {
				long ac = 0, bc = 0;
				while (lt < a.length && av == a[lt]) {
					ac++;
					lt++;
				}

				while (rt > -1 && bv == b[rt]) {
					bc++;
					rt--;
				}

				cnt += ac * bc;

			}

			if (av + bv < S) {
				lt++;
			} else if (av + bv > S) {
				rt--;
			}

		}

		if (S == 0)
			cnt--; // 부분집합의 요소가 없는 경우.
		System.out.println(cnt);

	}

}
ex)
5 0
-7 -3 -2 5 8
1


before sort
a의 부분 집합의 합 배열
0 -7 -3 -10 -2 -9 -5 -12 
b의 부분 집합의 합 배열
0 5 8 13 
after sort
a의 부분 집합의 합 배열
-12 -10 -9 -7 -5 -3 -2 0 
b의 부분 집합의 합 배열
0 5 8 13