백준_1182_부분수열의 합

문제: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

알고리즘: 브루트포스-재귀

 

📌 1번째 풀이

✔️로또 문제의 로직을 응용했다. 로또 문제는 선택해야 하는 개수가 6개로 정해져 있었지만, 부분수열의 합 문제는 부분수열의 길이가 정해져 있지 않으므로, for문으로 부분수열의 길이가 1, 2, ··· [수열의 길이] 일때 각각 재귀함수를 호출했다.

 

🚨for문 안에서 아래와 같이 벡터를 선언했더니 벡터에 push_back()이 안되었다.

for (int i = 1; i <= len; i++) {
	vector<int> sub(i);
	solve(arr, i, 0, 0, sub);
}

아래와 같이 길이를 미리 지정하지 않는 코드로 바꿨더니 제대로 동작했다.

for (int i = 1; i <= len; i++) {
	vector<int> sub;
	solve(arr, i, 0, 0, sub);
}

 

코드:

#include <iostream>
#include <vector>

using namespace std;

int len, sum, ans = 0;

void solve(vector<int>& arr, int subLen, int cnt, int index, vector<int>& sub) {
	// 정답 찾은 경우
	if (cnt == subLen) {
		// 합 검사
		int result = 0;
		for (int i = 0; i < subLen; i++) {
			result += sub[i];
		}
		if (result == sum) ans++;
		return;
	}
	// 불가능한 경우
	if (index == len) return;
	// 다음 호출
	// index번째 선택 O
	sub.push_back(arr[index]);
	solve(arr, subLen, cnt + 1, index + 1, sub);
	sub.pop_back();
	// index번째 선택 X
	solve(arr, subLen, cnt, index + 1, sub);
}

int main() {
	cin >> len >> sum;
	vector<int> arr(len);
	for (int i = 0; i < len; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= len; i++) {
		vector<int> sub;
		solve(arr, i, 0, 0, sub);
	}
	cout << ans << '\n';
	return 0;
}

 

📌 2번째 풀이 (Better!)

✔️ 이 문제에서는 로또 문제처럼 부분수열을 출력할 필요 없이, 합만 구하면 되므로(부분수열의 길이도 정해져 있지 않으므로), 굳이 부분수열을 저장할 배열을 만들 필요가 없다.

⭐ 주의해야 할 점: 합이 '0'이 되는 부분수열의 개수를 출력하는 문제라면 → 재귀함수에서 부분수열의 길이가 0인 경우도 세지므로 마지막에 답에서 1을 빼야함.

 

+ 또한, 부분수열을 어떤 순서대로 출력해야하는 문제가 아니므로, 재귀함수의 '다음 호출' 부분에서 index번째를 선택하는 경우와 선택 안하는 경우의 순서가 바뀌어도 상관 없음.

 

코드:

#include <iostream>
#include <vector>

using namespace std;

int len, sum, ans = 0;

void solve(vector<int>& arr, int subSum, int index) {
	// 반드시 모든 원소에 대해 선택했을 때 합 검사
	if (index == len) {
		// 합 검사
		if (subSum == sum) {
			ans++;
		}
		return;
	}
	// 다음 호출
	// index번째 선택 O
	solve(arr, subSum + arr[index], index + 1);
	// index번째 선택 X
	solve(arr, subSum, index + 1);
}

int main() {
	cin >> len >> sum;
	vector<int> arr(len);
	for (int i = 0; i < len; i++) {
		cin >> arr[i];
	}
	solve(arr, 0, 0);
	if (sum == 0) {
		ans--;
	}
	cout << ans << '\n';
	return 0;
}

 

위 코드의 solve 함수를 void형이 아닌 int형을 반환하는 함수로 바꾼 코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;

int solve(vector<int>& v, int idx, int sum) {
	int ans = 0;
	// 성공한 경우
	if (idx == N) {
		if (sum == M) {
			return 1;
		}
		return 0;
	}
	// 실패한 경우 X
	// 다음 호출
	ans += solve(v, idx + 1, sum + v[idx]);
	ans += solve(v, idx + 1, sum);
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	vector<int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	// M이 0이면, 아무것도 더하지 않는 경우도 포함되므로 -1 하기
	if (M == 0) {
		cout << solve(v, 0, 0) - 1 << '\n';
	}
	else {
		cout << solve(v, 0, 0) << '\n';
	}
	return 0;
}