(C/C++) 백준 1182번 - 부분 수열의 합

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

1182번: 부분수열의 합

1.코드

#include <iostream>

using namespace std;

int n, s;
int arr[20];
int cnt = 0;

// index : 선택한 숫자의 인덱스, sum: 합
void find(int index, int sum) {

	sum += arr[index];

	if (index >= n) return;

	if (sum == s) cnt++;

	//재귀호출 따로 따로
	find(index + 1, sum - arr[index]); // 해당 숫자를 안 더함
	find(index + 1, sum); // 해당 숫자를 더함
}


int main(void) {

	scanf("%d %d", &n, &s);

	for (int i = 0; i < n; i++) {
		scanf("%d",&arr[i]);
	}

	find(0, 0);

	printf("%d\n", cnt);
}

2. 해결과정

부분수열의 합이 s가 되는 경우의 수를 찾는 문제이다. 재귀함수를 이용해서 인덱스 값 1~n까지 차례대로 현재 인덱스의 수를 더하는 경우와 현재 인덱스의 수를 패스하는 경우에 대해서 각각 계싼을 해줬고, sum=s가 되면 카운트를 해주면 되는 문제였다.

 

3. 느낀점

연속된 수의 합을 찾는 것이 아니고, 부분집합의 합을 구하는 것이 아니라 중복이 포함된다는 점이 구현하기에 까다로웠던 부분이였다. 또한 재귀에 대해서 아직 잘 못해서 호출을 따로따로 해줘야 하는 것도 어려웠다. dfs에 대해서 다시한번 정리하는 시간을 가져야할듯하다.