백준 1182번 부분수열의 합

- 문제 설명

 

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

 

 

- 입력

 

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

 

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

 

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

 

 

- 출력

 

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

 

 

* 문제 풀이의 핵심

 

 

1. 브루트포스

 

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

 

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

 

약 100만개의 경우의 수는 가짓수가 얼마 되지 않기 때문에 재귀로 문제를 해결할 수 있습니다.

 

또한 부분 수열의 수를 사용한다 (1), 부분 수열의 수를 사용하지 않는다 (0) 으로 나누어 비트마스크로도 문제를 해결할 수 있습니다.

 

* 주의사항

 

: 크기가 양수인 부분수열을 구해야하기 때문에 아무것도 선택하지 않는 공집합일 때 합의 0 인 경우 정답이 될 수 없습니다.

 

 

2. 알고리즘 - 재귀로 구현

 

- find_sum 함수 구현

 

- 파라미터 : index -> 20개 수 중에서 사용할 인덱스, cur -> 현재 까지의 합, n -> 입력받은 N, sum -> 구해야할 S

 

<1> 정답인 경우 : 모든 부분집합을 사용할지 말지 결정 한 후 합이 S인 경우

 

ex) 합이 2 인 부분집합을 구하는 경우

2 -2 2

 

정답은 {2}, {2,-2,2} 두 가지 부분집합이 존재하는데, {2} 에서 정답을 찾았다고 뒤의 부분집합의 원소를 검사하지 않으면 안된다.

 

<2> 오답인 경우 : 모든 부분집합을 사용할지 말지 결정하였는데 합이 S가 되지 않는 경우

 

<3> 다음 경우의 수를 찾는 경우 : 

 

1) 현재 index의 수의 원소를 사용하고 더하는 경우

 

ex) 2, -2, 2

 

부분집합 {2, -2, 2} = {사용 O, 사용 O, 사용 O}

 

 

2) 현재 index의 수의 원소를 사용하지 않고 더하는 경우

 

ex) 2, -2, 2

 

부분집합 {2} = {사용 O, 사용 X, 사용 X}

 

 

위의 모든 조건을 만족하는 재귀식은 아래의 코드블럭과 같습니다.

 

 

int find_sum(int index, int cur, int n, int sum) {
	int ret = 0;
    // 현재합이 S 인 경우, 모든 부분집합을 다 사용한 경우
	if (cur == sum && index == n) return 1;
    // 모든 부분집합을 다 구한 경우, 합이 S가 되지 않는 경우
	if (index == n && cur != sum) return 0;

	// 현재 index 수의 원소를 사용해 더하는 경우
	ret += find_sum(index + 1, cur + number[index], n, sum);
	// 현재 index 수의 원소를 사용하지 않는 경우
    ret += find_sum(index + 1, cur, n, sum);

	return ret;
}

 

 

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

 

* 연산자 << : 왼쪽으로 1 비트 이동 (shift)

 

<1> 모든 가능한 비트 조합을 순회한다. (비트 조합 = 부분집합 경우의 수)

 

<2> 비트 조합 내 부분집합이 1이면 해당 부분수열의 원소를 사용하는 것이기 때문에 현재 합에 추가한다. (0이면 무시)

 

<3> 합이 S 이면 정답 경우의 수 추가

 

 

ex) N을 5라고 가정했을 때의 예시

 

- for문에서 i = 모든 부분수열의 경우의 수 = (1<<N) = 2^N = 32

 

0 : 00000 (공집합이므로 1부터 시작)

1 : 00001

2 : 00010

...

32 : 11111

 

 

- for문에서 j = 해당 원소를 사용하는지 하지 않는지 검사하는 반복문

 

ex) 배열 : [-7, -3, -2, 5, 8]

 

i = 01101 = 13

 

(1 << j) = 0 = 00001

(1 << j) = 1 = 00010

(1 << j) = 2 = 00100

(1 << j) = 3 = 01000

(1 << j) = 4 = 10000

 

=> i 부분집합을 j 반복문으로 검사한 후에는 배열에서 -3, -2, 8 을 사용한 것을 알 수 있다.

 

 

위의 모든 조건을 만족하는 비스마스크 구현은 아래의 코드블럭과 같습니다.

 

 

for (i = 1; i < (1 << N); i++) {
  int sum = 0;
  for (j = 0; j < N; j++) {
    if (i & (1 << j)) {
    	sum += num[j];
    }
  }
  if (sum == S) answer += 1;
}

 

 

- 소스코드 - 재귀로 구현

 

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

using namespace std;

int number[21];

int find_sum(int index, int cur, int n, int sum) {
	int ret = 0;
	if (cur == sum && index == n) return 1;
	if (index == n && cur != sum) return 0;

	ret += find_sum(index + 1, cur + number[index], n, sum);
	ret += find_sum(index + 1, cur, n, sum);

	return ret;
}

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

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

	int answer = find_sum(0, 0, N, S);
	if (S == 0) answer -= 1;
	cout << answer << "\n";
}

 

 

 

- 소스코드 - 비트마스크로 구현

 

#include<iostream>

using namespace std;

int num[21];

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

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

	int answer = 0;
	for (i = 1; i < (1 << N); i++) {
		int sum = 0;
		
		for (j = 0; j < N; j++) {
			if (i & (1 << j)) {
				sum += num[j];
			}
		}

		if (sum == S) answer += 1;
	}

	cout << answer << "\n";
}

 

 

 

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

1182번: 부분수열의 합

 

 

- 제출한 코드

 

재귀로 구현한 코드

 

비트마스크로 구현한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

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