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

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

 

---

우선 부분수열의 개념부터 보도록 하자. 

부분 수열이란? ' 부분수열은 주어진 수열에서 일부 또는 전체 원소를 원래 순서대로 뽑아 만든 새로운 수열을 말합니다.'

{a, b, c}라는 집합에서 부분 수열은 {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} 공집합 이렇게 된다. {b, a}는 부분 수열이 아니다. 순서대로 뽑지 않았기 때문이다.

 

그럼 이제 문제를 어떻게 풀지 접근해보도록 하자.

{1, 2, 3} 이있을 때 4를 만족하는 부분 수열의 개수를 구하기 위해서 {1, 3}을 뽑으면 된다는 것을 직관적으로 알 수 있는데 이를 코드로 나타내기 위해서는 '백트래킹'이 필요하다. (n이 20이기 때문에 비트마스킹을 통한 brute force방법도 있다.)

즉 1을 뽑았다가 2도 뽑고 3도 뽑아보고 조건에 안 맞으면 다시 되돌아와서 2를 뽑지 않고 3을 뽑아보는 식이다.

 

 

위 그림을 코드로 나타내면 아래와 같다.

 

---

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

const int MAX = 22;
int n, s, ret, arr[MAX];

void Func(int idx, int nowSum)
{
	if (idx >= 0 && nowSum == s)
	{
		++ret;
	}
	
	for (int i = idx + 1; i < n; ++i)
	{
		Func(i, nowSum + arr[i]);
	}
}

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    
	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	Func(-1, 0);
	cout << ret << endl;
}

 

이렇게 풀어도 {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}의 경우를 다 따질 수 있는데 다른 방법도 있다.

로직은 거의 똑같은데 뽑거나 안뽑는 식의 로직으로도 구성할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int n, s, arr[30], ret;

void Func(int curIdx, int sum)
{
	if (curIdx == n)
	{
		if (sum == s) ++ret;
		return;
	}
	
	Func(curIdx + 1, sum);					// curIdx번째 수를 뽑지 않는다. 
	Func(curIdx + 1, sum + arr[curIdx]);	// curIdx번째 수를 뽑는다. 
}
 
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    
	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> arr[i];

	Func(0, 0);
	if (s == 0) ret--; // s가 0인경우 공집합도 0이 되기 때문에 하나를 빼준다. 
	cout << ret;
}

 

마지막 풀이로 비트 마스킹 풀이도 있다.

n이 20이라는 점을 활용하여 BruteForce로 푸는 방법이다.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int n, s, ret;
int arr[22];

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    
	cin >> n >> s;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	
	for (int mask = 1; mask < (1 << n); ++mask)
	{
		int sum = 0;
		for (int i = 0; i < n; ++i)
		{
			if (mask & (1 << i))
			{
				sum += arr[i];
			}
		}
		if (sum == s) ++ret;
	}
	
	cout << ret << endl;
}

위의 예에서 {1, 2, 3}인경우 비트를 왼쪽으로 3번밀면 8인데 1~7까지 mask값을 증가시킨다. 그럼 mask는

0001, 0010, 0011, 0100, 0101, 0110, 0111 까지를 표현하게 된다. 즉 공집합을 제외한 모든 가짓수를 표현할 수 있고 이를 i와 비트 마스킹 하면 모든 경우의 수를 따질 수 있다.