[백준/JAVA] 1208_부분수열의 합2

백준🔗

1208번: 부분수열의 합 2

 

 

문제

 

 

간단 풀이

2023.07.03 - [알고리즘/백준] - [백준/JAVA] 1182_부분수열의 합

☝️이 문제를 풀어보려다 감이 잘 오지 않아서 "부분수열의 합"을 먼저 풀고 왔다.

두 문제는 얼핏 보면 똑같은 문제처럼 보이지만 한 가지 다른 점이 있다. N의 범위가 최대 40으로 2배가 된 것인데 이게 어떤 의미를 가지는지 먼저 생각해 보았다.

 

원소가 N개인 수열은 2^N개의 부분수열을 갖는다. N이 20일 때는 2^20, 즉 대략 100만개의 부분수열이 있기 때문에 모든 부분수열에 대해 완전탐색을 진행해도 문제를 충분히 풀어낼 수 있었다. 그러나 N이 40이 되면 2^40은 대략 1조.. 허헣.. 절대절대 완전탐색을 할 수 없는 규모다..

 

그렇다면 어떤 방법을 적용해야 할지 열심히 고민해 봤지만 마땅한 방법이 떠오르지 않아서 다른 분들의 코드를 조금 참고해봤다.

 

해결방법은, 주어진 수열을 반으로 나눠서 해결하는 것이다!

반으로 나누면 하나의 수열이 최대 2^20개의 부분수열을 갖기 때문에 각각에 대해서는 훨씬 적은 시간에 부분수열들의 합을 구할 수 있다.

이렇게 각각 구한 뒤에도 부분수열들의 조합을 완전탐색으로 찾으면 시간초과가 발생하겠지만, 투포인터를 적용한다면 시간을 줄일 수 있다.

아래에 풀이 과정을 정리해 봤다.

 

1) 주어진 수열을 반으로 나눠서 각각의 부분수열들의 합을 L, R 배열에 저장한다.

2) L, R을 오름차순 정렬한다.

3) 2개의 포인터를 사용해서 하나의 포인터는 L의 앞부터(작은 수부터), 다른 포인터는 R의 뒤부터(큰 수부터) 시작하여 탐색을 진행한다.

4) 두 포인터가 가르키는 합이 

    4-1) S보다 큰 경우, R에서 진행 중인 포인터를 하나 왼쪽으로 이동시킨다.

    4-2) S보다 작은 경우, L에서 진행 중인 포인터를 하나 오른쪽으로 이동시킨다.

    4-3) S인 경우, 각각의 포인터의 앞뒤로 같은 값들이 존재할 수 있기 때문에 이들의 개수를 세줘야 한다.

           L에서 진행 중인 포인터는 오른쪽으로 이동하며 같은 값의 개수를 leftCnt에 저장한다.

           R에서 진행 중인 포인터는 왼쪽으로 이동하며 같은 값의 개수를 rightCnt에 저장한다.

           => 원소의 합이 S가 되는 부분수열의 개수는 leftCnt * rightCnt개가 된다.

5) 범위 끝까지 진행한 후 cnt를 출력한다. (여기서 S가 0인 경우는 왼쪽과 오른쪽 그룹이 모두 공집합인 경우도 포함한다. "크기가 양수인 부분수열 중에서"라는 조건이 있기 때문에 이 경우는 -1 해줘야 한다.)

 

그리고 마지막으로 한 가지 주의할 점은, 위에서도 얘기했듯이 부분집합의 총 개수가 최악의 경우 2^40(대략 1조)개가 되기 때문에 int 범위를 초과하게 된다. 따라서 부분수열의 개수를 카운트하는 변수의 타입은 ⭐long⭐으로 정해야 오버플로우가 발생하지 않는다!! 

 

코드

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

public class Main {
	static int N, S;
	static int[] arr;
	static int[] L, R;

	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()); // 합이 S인 부분수열 개수 구하기
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 수열 2개로 쪼개기
		L = new int[(int) Math.pow(2, N / 2)];
		R = new int[(int) Math.pow(2, N - N / 2)];
		getPartPerm(L, 0, N / 2 - 1);
		getPartPerm(R, N / 2, N - 1);

		// 왼쪽, 오른쪽 부분수열의 합들 오름차순 정렬
		Arrays.sort(L);
		Arrays.sort(R);

		// 투포인터로 비교하며 합이 0이 되는 조합 찾기
		long cnt = 0;
		int leftP = 0;
		int rightP = R.length - 1;
		while (leftP < L.length && rightP >= 0) {
			int leftVal = L[leftP];
			int rightVal = R[rightP];
			if (leftVal + rightVal > S) {
				rightP--;
			} else if (leftVal + rightVal < S) {
				leftP++;
			} else {
				long leftCnt = 0;
				long rightCnt = 0;
				// L 또는 R 내에 값이 같은 경우가 있을 수 있음
				while (leftP < L.length && leftVal == L[leftP]) {
					leftP++;
					leftCnt++;
				}
				while (rightP >= 0 && rightVal == R[rightP]) {
					rightP--;
					rightCnt++;
				}
				cnt += (leftCnt * rightCnt);
			}
		}

		// "크기가 양수인 부분수열 중에서" 구해야 하기 때문에 L, R 모두 공집합인 경우는 제외해야 함
		System.out.println((S == 0) ? cnt - 1 : cnt);
	}

	static void getPartPerm(int[] Arr, int st, int ed) {
		int n = ed - st + 1;
		// 비트마스킹으로 부분순열 구하기
		for (int i = 0; i < (1 << n); i++) { // 부분집합 i (공집합 포함)
			int sum = 0; // 부분집합 i에 포함되는 원소들의 합
			for (int j = st; j <= ed; j++) { // j번째 원소
				// 부분집합 i에 j번째 원소가 포함되는 경우
				if ((i & (1 << (j - st))) > 0) {
					sum += arr[j];
				}
			}
			Arr[i] = sum;
		}
	}
}

 

참고 자료

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

 

[백준 1208번] 부분수열의 합 2 (java)