[BOJ].1182 부분수열의 합

첫 블로그 글이다.. 알고리즘으로 시작하지만 다른 내용으로도 가득 찼으면 좋겠다.

오늘 인상깊게 풀었던 BitMask와 관련된 문제이다.
문제에 대한 설명은 생략하고 바로 본론으로 들어가겠다.

일단 이 문제를 BitMask로 해결할 때 핵심은
핵심1. "n개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열의 개수는 2^n-1개이다."
핵심2. "위 개수를 조합 식으로 표현하면 nC1+nC2 .... nCn이 된다."
핵심3. "1부터 2^n-1까지 2진법으로 표현했을 때 1이 위치한 곳은 수열에서 선택한 원소의 위치와 똑같다.

조금 생각해보면 아마 어렵지 않을 것이다. 그림으로 한 번 보자.

예를 들어 n이 4일 때

가능한 경우의 수는 15개가 나오고 이에 해당하는 2진 숫자를 위와 같이 표현하였다.

위 2진 숫자중 아무거나 하나 뽑아오겠다.

2진수를 좀 지켜보니 1이 위치한 idx번호를 수열에서 선택할 idx번호로 쓸 수 있다는 것을 알 수 있다.

뭐 이런식으로 말이다.

그러고 나서 저 2진 숫자를 1의 개수에 따라 정리했을 때 핵심2의 식을 도출할 수 있게 되었다.
동시에 파스칼 삼각형도 생각이 났었다.

이제 비트연산자를 써야하는데, 비트연산자 문법은 어렵지 않으니 스스로 공부해보자.

핵심코드
1. i < (1 << n) : 2^n-1의 경우의 수
2. IF ( i & ( 1 << j ) ) : 부분수열을 찾는 조건

아마 여기까지 이해했다면 나머지 코드를 이해하는데 문제는 없을 것이다.
뭔가 복잡할 것 같았는데 알고나니 엄청 복잡한 수준은 아니였다.
그리고 1,0을 조합의 수로 사용할 수 있다는 점도 처음 알게 되었다. 상황에 따라 써먹기 좋을 듯 하다.

BitMask 코드

#include <iostream>

using namespace std;


int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n, s;
	int arr[21];

	cin >> n >> s;

	int i, j, cnt = 0;;

	for (i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (i = 1; i < (1 << n); i++) {

		int sum = 0;

		for (j = 0; j < n; j++) {

			if (i & (1 << j)) {
				sum += arr[j];
			}
		}

		if (sum == s) {
			cnt++;
		}
	}

	cout << cnt;

	return 0;



}

DFS 코드

요건 DFS로 푼 방식.
s가 0일 때 하나도 선택 안된경우에 대해 cnt가 하나증가 함으로
cnt--를 해줘야한다!

#include <iostream>

using namespace std;

int n, s;
int arr[21] = { 0 };
int cnt = 0;

void DFS(int depth, int sum) {

	if (depth > n) {
		
		if (sum == s) {
			cnt++;
		}
		return;
	}
	
	DFS(depth + 1, sum);
	DFS(depth + 1, sum+arr[depth]);
}

int main() {

	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> n >> s;
	
	int i;

	for (i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	DFS(1, 0);

	if (s == 0) cnt--;
	cout << cnt;

	return 0;
}