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

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

1182번: 부분수열의 합

 

정수들의 개수와 목표로 하는 합을 입력받는다.

 

정수들로 만들 수 있는 길이가 1 이상인 부분 수열들을 구한다. 그리고 그 부분수열들의 합이 처음에 입력받은 S와 같은 부분수열의 개수를 구하면 되는 문제이다.

 

우선 N개의 숫자를 입력받았다고 가정하면, 1개, 2개, 3개 ... N개로 만들 수 있는 부분수열을 모두 구해야 한다.

 

그리고 매 부분수열마다 합을 계산해서 그 합이 s인지 아닌지 판단해주면 되는 문제이다.

 

즉 조합으로 바꿔서 생각할 수 있고, n이 20 이하로 작으니 백트래킹을 해도 무방하다.

 

직접 재귀로 구현할 수도 있지만 next_permutation을 이용해서 구현했다.

 

 

Sel 배열을 우선 만들어 둔다. 가령 6개 중에 4개를 조합으로 뽑는다면,

 

Sel 배열은 0, 0, 0, 0, 1 1 이렇게 두고 if(!Sel[i]) 일 때 수열이 만들어지게 된다.

 

이를 이용해서 1개부터 n개까지 부분수열을 구해주면 되겠다.

 

 

#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a[20], Sum = 0, Sel[20], cnt = 0;
int main(void) {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 20; i++)
		Sel[i] = 1;
	for (int i = 0; i < n; i++) {
		Sel[i] = 0; //하나씩 0으로 바꿈
		do {
			Sum = 0;
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) Sum += a[j];
				//if (!Sel[j]) cout << a[j] << ' ';
			}
			if (Sum == s) cnt++;
		} while (next_permutation(Sel, Sel + n));
	}
	cout << cnt << '\n';
	return 0;
}