[비트마스크] 1182 부분 수열의 합

부분 수열의 합 (1182)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1182 부분수열의 합

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int n, s;
	
	cin >> n >> s;
	cin.ignore();
	
	int arr[20];
	
	for(int i = 0 ; i < n; i++){
		cin >> arr[i];
	}
	int ans = 0;
	
	for(int bm = 1; bm < (1 << n); bm++){
		int sum = 0;
		for(int i = 0; i < n; i++){
			// bm 에 i 가 들어있으면
			if(bm & ( 1 << i )){
				// sum 에 추가
				sum += arr[i];
			}
		}
		if(sum == s) ans++;
	}
	cout << ans << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

1. n 의 크기가 최대 20으로 작으므로 비트마스크를 사용할 수 있겠다.

2. n 크기의 비트마스크를 0 부터 n 까지 순회해보자. ( 하지만, 문제에서 말했듯이 공집합 0 은 제외해야 함)

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점