[C++]백준 1182번: 부분수열의 합

문제

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

1182번: 부분수열의 합

문제이해

• 첫째 줄에 정수의 개수와 합으로써 원하는 값을 입력한다.
• 두 번째 줄에는 정수의 개수만큼의 수를 입력한다.
• 출력으로 부분 수열의 합이 원하는 값이랑 똑같았던 경우가 몇 번인지 출력한다.

수에 딱히 규칙성도 없고 무작위의 수중에서 무작위 수만큼을 골라 원하는 값이 나오는지 확인해야 하기 때문에 브루트포스 알고리즘을 사용하여야 한다.

 

브루트포스 알고리즘이란 가능한 모든 경우의 수를 일일이 전부다 검사하여 답을 찾는 방식을 말한다.

예제 입력 1을 예시로 들자면 -7을 합하거나 합하지 않거나 -3을 합하거나 합하지 않거나.... 8을 합하거나 합하지 않거나 이렇게 하여 0이 나오는 경우가 몇 개인지 확인해야 된다.

 

문제해결

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

int count_{};
vector<int> numbers;

void includeN(int target, int index, int sum, int check) {
	if (index > numbers.size() - 1) {
		if (target == sum) {
			if (check != numbers.size()) {
				count_++;
			}
		}
		return;
	}
	includeN(target, index + 1, sum, check + 1);
	includeN(target, index + 1, sum + numbers[index], check);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, targetN, input;
	cin >> N >> targetN;
	for (int i{ 1 }; i <= N; i++) {
		cin >> input;
		numbers.push_back(input);
	}
	includeN(targetN, 0, 0, 0);
	cout << count_;
}

void includeN

해당 함수는 재귀적으로 구현되어 있으며, 주어진 인수로는 목표로 하는 값인 'target'과 현재 처리 중인 'vector'의 인덱스인 'index'가 있으며, 현재까지 더해진 수의 합을 저장하기 위한 'sum' 변수와 모든 수가 한 번도 더해지지 않은 경우를 제거하기 위한 'check' 변수도 사용됩니다.

이 함수는 현재 처리 중인 'vector'의 'index' 값을 더하는 경우와 더하지 않는 경우로 나뉘어져 있습니다. 재귀 호출을 통해 이러한 분기 처리가 이루어집니다.

문제후기

재귀함수로 구현한다면 간단하게 해결할 수 있는 문제였습니다.