[BaekJoon]1182번: 부분 수열의 합

브루트포스 알고리즘

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다.
(1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.
주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1 
5 0
-7 -3 -2 5 8

예제 출력 1 
1

💻코드

#include<iostream>	
#include<algorithm>
#include<vector>
#include<string>	

using namespace std;

int main(void) {
	int N, S;           // 원소 개수, 원소 합
	vector<int> num;    // 수열
	int i, j, sum;      
	int cnt = 0;        // 경우의 수

    // 원소 개수, 합, 수열 입력받기
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		num.push_back(tmp);
	}

    // 부분 수열의 개수만큼 반복문을 돌면서 부분수열 합을 구한다
	for (i = 1; i < (1 << num.size()); i++) {
		sum = 0;    // 합 초기화

		for (j = 0; j < num.size(); j++) {
			if (i & (1 << j)) sum += num[j];
		}
		if (sum == S) {
			cnt++;
		}
	}
	cout << cnt;

	return 0;
}

변수	역할
N	원소 개수 저장
S	원소 합 저장
num	수열 저장
i, j, sum	반복문에서 사용하는 변수
cnt	합이 S와 일치하는 부분 수열의 개수 세는 변수

• 부분 수열 합 계산
  i < (1 << num.size())으로 부분 수열 개수만큼 반복하는데, i는 이진수 표현으로 부분 수열의 포함 여부를 나타낸다. 예를 들어, i가 3이면 이진수로 011이고 이것은 num[0]과 num[1]로 이뤄진 부분 수열임을 나타낸다. 그래서 i가 부분수열 개수만큼 반복되는 것이다. 이 때, j를 0부터 증가되면서 and 연산자를 통해 i의 이진수 표현에서 1에 해당하는 원소를 더하게 되는 것이다.

            v = 1 3 5
            i = 0 1 1      
        j = 0   0 0 1 -> & = 001 = 1 -> v[j] = 1 더해짐
        j = 1   0 1 0 -> & = 010 = 2 -> v[j] = 3 더해짐
        j = 2   1 0 0 -> & = 000 = 0 
  

  v = 1 3 5, i = 3(011), j = 0 일 때, i는 수열 {1,3,5}에서 부분수열 {1, 3}을 나타낸다. 1 << j 연산을 통해 각 원소 자리의 숫자만 1이 되고 & 연산을 통해 포함되었는지 아닌지 알 수 있게 된다.

비트 연산과 비트로 생각하는 것이 익숙치 않아서 이해하는 데 꽤 오래 걸렸다. 나중에 다시 보면 또 까먹고 방황할 것 같다..