[백준/c++] 1182번: 부분수열의 합

 

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

1182번: 부분수열의 합

 

크기가 양수 == 부분 수열 속 원소 1개 이상 (1개 가능)

주의) 연속된 부분 수열이 아님

 

 

[백트래킹]

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[21], s, ans = 0;

void BT(int cnt, int sum){
    if(cnt == n){ //arr의 끝까지 간 경우
        if(sum == s) ans++;
        return;
    }
    
    BT(cnt+1, sum + arr[cnt]);  //현재 수열 더하기
    BT(cnt+1, sum);             //현재 수열 더하지 않기
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for(int i=0; i<n; i++) cin >> arr[i];
    BT(0, 0);
    if(s==0) ans--;
    cout << ans << '\n';
    return 0;
}

 

---

 

 

[비트 마스킹] - 백트래킹으로 풀었다. 비트마스킹으로도 할 수 있길래 찾아봤다.

이전에 했던 비트마스크 문제를 생각해보면 해당 수를 자릿수(1)로 바꾸는 방식이었다.

예를 들어, {2, 4, 6} = 1010100

(1<<N) : n을 n번째 자릿수로 생각하기 위해서이다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, arr[21], s, ans = 0;
    cin >> n >> s;
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int i=1; i<(1<<n); i++){ //1부터 시작 = 공집합 제외
        int sum = 0;
        for(int j=0; j<n; j++){ //0 ~ n-1 돌면서 해당 부분집합이 어떤 index의 원소를 가지는지 확인
            if(i & (1<<j)) sum += arr[j]; //부분집합에 들어있으면 해당 값을 더해준다.
        }
        if(sum == s) ans++;
    }
    cout << ans << '\n';
    return 0;
}

 

 

이렇게 비트마스킹하는 문제들을 봤는데 대체로 i라는 수가 집합 안에 있는지 없는지를 확인하는 부분에 많이 사용하는 것 같다.

많이 나오는 형태: 

(1<<n)

for문 내에서 if(i & (1<<j)) : 경우의수에 해당하는지 or 집합 안에 있는지 없는지

 

 

그런데 백트래킹으로 충분히 잘 되므로 백트래킹만 해도 괜찮을 거 같다.^^