[백준문제풀이] 1182 부분수열의 합

 

풀이일시 : 2020-12-23

​

 

문제 :

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

​

​

입력 :

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

ex)

5 0

-7 -3 -2 5 8

​

​

출력 :

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

ex)

1

​

 

풀이 :

부분수열을 구하는 문제, 순열을 구하는 문제가 나올때마다 계속해서 next_permutation을 생각하게 되는데 여기서는 정상적인 접근이 아니다.. 재귀를 통한 완전탐색으로 건드려보자.

​

hap함수에서 동작을 살펴보자.

입력 :
5 0
-7 -3 -2 5 8

1. (0,0)으로 시작해준 뒤 0번째의 원소를 b에 합해준다. b+=arr[0]

2. 만약 a가 N과 같거나 이상이라면 (범위달성) return 시켜준다.

3. 만약 b가 정답인 S와 같다면 갯수를 증가시켜준다.

4. 이후 값을 더하지 않고 다음 값으로 넘어가기 or 값을 더하고 다음값으로 넘어가기 방법이 존재한다.

- 값을 더하고 넘어왔다 하면

1. (1, -7) 으로 시작해준 뒤 1번째의 원소를 b에 합해준다. b+=arr[1] = -7

2. a가 갯수를 달성하지 못했으니 return X

3. b가 0이 아닌 -7 이므로 넘어간다.

4. 이후 값을 더하지 않고 다음 값으로 넘어가기 or 값을 더하고 다음값으로 넘어가기 방법이 존재한다.

계속해서 진행하면 완전탐색이 가능할것이다.

​

완전탐색의 방법이 확실히 이해가지 않았다면 아래 조잡한 그림을 보면 이해갈 수 있을것이다.

위 그림은 input 을 4 0 / -7 -3 -2 5 로 준 것이다. 처음이 아니고 B가 0인 경우에 CNT가 ++ 된 것을 볼 수 있다. 이와같이 완전탐색을 계속해나가며 B=0일때만 CNT를 ++ 해주면 될것이다.

​

//부분수열구하기
#include <iostream>

using namespace std;

const int MAX = 20;

int N, S;
int arr[MAX];
int cnt = 0;

void hap(int a, int b) {
	b += arr[a];
	if (a >= N) { //만족하면 return해주기
		return;
	}
	if (b == S) {
		cnt++;
	}
	//두갈래길로 나뉘게된다.
	hap(a + 1, b - arr[a]); //안더해주고 다음 인덱스로넘어가기
	hap(a + 1, b); //더해주고 다음인덱스로 넘어가기

}

int main() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	hap(0, 0);
	cout << cnt << endl;
	return 0;
}

 

참고자료 : BP

dbstndi6316.tistory.com/36

[개념정리] BP 브루트 포스 알고리즘