[BOJ 1182] 부분수열의 합

1) 문제 링크

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

2) 접근

걍 재귀로 노가다하면 되겠지~ 생각했다. 숫자 20개니까 2^20이면 얼마 안 되거든.

3) 풀이

아래는 처음 짰던 코드다.

#include <iostream>
using namespace std;

int n, s;
int arr[20];

int solve(int sum, int idx, int cnt){
    // base case 1: 조건 만족 -> +1
    if(cnt && sum == s) return 1;
    // base case 2: 밑바닥 도달 but 불일치 -> X
    if(idx == n - 1) return 0;

    return solve(sum+arr[idx+1], idx+1, cnt+1)+solve(sum, idx+1, cnt);
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    // index -1로 해서 tree의 root node 역할로 재귀 시작
    cout << solve(0, -1, 0);

    return 0;
}

‘혹시 원소가 동일한 수열의 합은 1가지로 처리되는 거 아닐까?’ 하는 쓸데없는 의심을 시작으로 코드가 점점 산으로 갔는데, 고민 끝에 찾아보니까 그냥 합이 0인 경우 공집합 예외처리를 제대로 하지 않아서 생긴 문제였다.
‘공집합은 제외? -> 공집합이 해집합에 포함될 수 있는 경우가 뭐가 있지? -> 합이 0인 경우가 유일!’ 이 사고과정이 제대로 안 돌아갔던 것.

#include <iostream>
using namespace std;

int n, s;
int arr[20];
int cnt;

void solve(int idx, int sum){
    if(idx == n){
        if(sum == s){
            ++cnt;
        }
        return;
    }
    solve(idx+1, sum+arr[idx]);
    solve(idx+1, sum);
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s;
    for(int i=0; i<n; ++i){
        cin >> arr[i];
    }
    solve(0, 0);
    if(s == 0) { --cnt; }
    cout << cnt;

    return 0;
}

4) 피드백

비트마스크? 이용해서 푸는 방법도 있는 거 같고…
이렇게 신기하게 전체 경우를 탐색하는 방법도 있다.