백준 1208번 부분수열의 합 2

- 문제 설명

 

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

- 입력

 

1) 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000)

 

2) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.

 

* 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

 

- 출력

 

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

 

* 문제 풀이의 핵심

 

 

1. 브루트포스

 

부분수열의 합 2 문제는 주어진 집합의 모든 부분수열을 구한 뒤 더한 값이 S가 되는지 되지 않는지에 대해서 검사해야하는 문제 입니다.

 

N의 제한은 1에서 시작해 최대 40 이기 때문에 집합을 '사용한다', '하지않는다'의 두 가지 경우로 나누어 보면 2⁴⁰ (= 약 1조) 개의 경우의 수로 나타납니다.

 

부분수열의 합(1182) 문제와는 다르게 N 제한이 크기 때문에 모든 경우의 수를 다 확인하기에는 시간이 너무 오래 걸립니다.

 

그래서 절반으로 나누어서 경우의 수를 계산해 주어야 합니다. 40개의 수열을 20개 수열 2개로 나누어서 부분수열의 합을 계산해야 총 경우의 수가 2 * 2²⁰ (약 2백만) 이 되므로 제한시간 이내에 해결할 수 있습니다.

 

 

* 주의사항

 

: 합이 0 이 될때는 공집합인 경우도 될 수 있기 때문에 구한 정답에서 1을 빼주어야 합니다.

 

 

2. 알고리즘 - 비트마스크로 구현

 

<1> N 개의 수열을 절반으로 나누고, 절반으로 나눈 2개 집합의 모든 부분수열의 합을 각 각 구한다.

 

1) 수열을 up, down 집합으로 나누었다.

 

2) 수열이 홀수가 될 수 있기 때문에 up 배열의 크기는 N / 2, down 배열의 크기는 N - up_size 가 되어야 한다.

 

3) (1 << size) 만큼 배열을 할당하고 비트가 1 인 경우에 값을 계속 누적해주면 부분수열의 합을 구할 수 있다.

 

 

int up_size = N / 2;
int down_size = N - up_size;

vector<int> up(1 << up_size);
vector<int> down(1 << down_size);

for (i = 0; i < (1 << up_size); i++) {
  for (j = 0; j < up_size; j++) {
    if (i & (1 << j)) {
    	up[i] += A[j];
    }
  }
}

for (i = 0; i < (1 << down_size); i++) {
  for (j = 0; j < down_size; j++) {
    if (i & (1 << j)) {
    	down[i] += A[up_size + j];
    }
  }
}

 

 

* down 집합의 부분수열의 합이 A[up_size + j] 인 이유?

 

ex) N 이 5 라고 했을 때 up_size = 2, down_size = 3 이다.

 

up 집합의 부분수열의 합을 구할 때는 A 배열의 0~1 까지의 수를 사용하였다. (0 <= j < up_size)

 

그렇게 되면 down 집합에서는 나머지 2,3,4 수열의 부분수열의 합을 구해야 하기 때문에 up_size 만큼 더한 값 부터 부분수열의 합을 구하면 된다.

 

=> A[up_size + j] 라는 식을 사용하면 A 배열의 2,3,4 원소로만 부분수열의 합을 구할 수 있다.

 

(up_size = 2, 0 <= j < down_size)

 

 

<2> 두 개의 집합에 대응되는 left, right 변수를 사용해서 부분수열의 합을 구한다.

 

1) 두 집합의 부분수열의 모든 경우의 수를 찾았다면 up 집합은 오름차순, down 집합은 내림차순으로 정렬해준다.

 

2) 찾으려는 부분수열의 합 S 를 구할 때 left, right 를 갱신해준다.

 

2-1) up[left], down[right] 의 합이 S 인 경우 (정답을 찾은 경우)

 

: 만약 앞뒤 숫자가 같다면 길이를 찾는다. (조합할 수 있는 가짓수가 곱하기 연산을 해야하기 때문)

 

ex) S = 3, left = 1, right = 0

0 1 1

2 2

 

이 경우 합이 3 이 될 수 있는 부분수열의 개수는 4개입니다.

 

(left,right) = (1,0), (1,1), (2,0), (2,1)

 

left = 1, right = 0 일 때 개수를 1 증가시키고 left, right 값을 모두 1 증가시키게 되면 찾을 수 있는 경우의 수는 2개 입니다.

 

 

: left, right 값을 모두 1 증가시키고 answer 의 값을 증가시킨다. 

 

 

2-2) up[left], down[right] 의 합이 S 보다 작은 경우 left를 증가시킨다.

 

: left 는 오름차순이기 때문이다.

 

2-3) up[left], down[right] 의 합이 S 보다 큰 경우 right를 증가시킨다.

 

: right 는 내림차순이기 때문이다.

 

 

int left = 0, right = 0;

while (left < up.size() && right < down.size()) {
  if (up[left] + down[right] == S) {
    long long l_size = 1;
    long long r_size = 1;

    left += 1;
    right += 1;
    while (left < up.size() && up[left] == up[left - 1]) {
      l_size += 1;
      left += 1;
    }
    while (right < down.size() && down[right] == down[right - 1]) {
      r_size += 1;
      right += 1;
    }

    answer += (l_size * r_size);
  }
  else if (up[left] + down[right] < S) {
  	left += 1;
  }
  else {
  	right += 1;
  }
}

 

 

<3> long long 변수를 사용해야하는 이유

 

모든 경우의 수는 최대 2⁴⁰ 가지 경우가 나올 수 있기 때문에 answer, l_size, r_size 의 값을 int 형으로 하게 되면 범위가 초과된 값을 계산할 수 없기 때문에 정답을 맞출 수가 없습니다. 

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<queue>
#include<tuple>

using namespace std;

int A[41];

int main() {
	int N, S;
	cin >> N >> S;

	int i, j;
	for (i = 0; i < N; i++) {
		cin >> A[i];
	}

	int up_size = N / 2;
	int down_size = N - up_size;

	vector<int> up(1 << up_size);
	vector<int> down(1 << down_size);

	for (i = 0; i < (1 << up_size); i++) {
		for (j = 0; j < up_size; j++) {
			if (i & (1 << j)) {
				up[i] += A[j];
			}
		}
	}

	for (i = 0; i < (1 << down_size); i++) {
		for (j = 0; j < down_size; j++) {
			if (i & (1 << j)) {
				down[i] += A[up_size + j];
			}
		}
	}

	sort(up.begin(), up.end());
	sort(down.begin(), down.end());
	reverse(down.begin(), down.end());

	long long answer = 0;

	int left = 0, right = 0;

	while (left < up.size() && right < down.size()) {
		if (up[left] + down[right] == S) {
			long long l_size = 1;
			long long r_size = 1;

			left += 1;
			right += 1;
			while (left < up.size() && up[left] == up[left - 1]) {
				l_size += 1;
				left += 1;
			}
			while (right < down.size() && down[right] == down[right - 1]) {
				r_size += 1;
				right += 1;
			}

			answer += (l_size * r_size);
		}
		else if (up[left] + down[right] < S) {
			left += 1;
		}
		else {
			right += 1;
		}
	}

	// 공집합인 경우 제외
	if (S == 0) answer -= 1;
	cout << answer << "\n";
}

/*
6 4
1 2 1 3 1 2

*/

 

 

 

- 문제링크 : www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

 

- 제출한 코드

 

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요