3주차(백트래킹) - [C++]백준1182 부분수열의 합

17 Mar 2022 in Study on Algorithm

백준1182 부분수열의 합 링크

문제

예제 입력

---

코드

#include <iostream>
#include <vector>
using namespace std;

int n, s; // 원하는 값=s
int cnt = 0;
vector<int> arr;

void subsequence(int index, int sum) {
	if (index == n) {
		return;
	}
	// 원하는 값이면 카운트
	if (sum + arr[index] == s) {
		cnt++;
	}
	// 값을 넣었냐 / 넣지 않았냐로 나눔
	subsequence(index + 1, sum + arr[index]);
	subsequence(index + 1, sum);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		arr.push_back(num);
	}
	//부분수열의 합
	subsequence(0, 0);
	cout << cnt;
}

설명

이 문제는 수열이 있는데 그중 일부의 원소들로 만들어지는 부분수열의 합이 원하는 값인 경우 카운트해줍니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 스터디에서 백트래킹이라고는 했지만 백트래킹의 장점은 모든 것을 다 확인안하는데에 이점이 있는데 그렇게 풀지 않은 것 같습니다. 수열은 점점 값이 커지니 이미 값을 넘겼으면 확인을 안하는 것을 넣어주면 될 것같습니다.

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과