BOJ 1182번 : 부분수열의 합

N개의 정수 원소가 있는 수열에서 부분수열의 합이 S와 같은 경우의 수를 찾는 문제이다.

 

연속적인 수열이 아니므로, 모든 부분수열을 찾는 과정이 필요하다. 모든 것을 다 해보는 방법을 Brute-Force(완전탐색)이라고 한다.

 

일단, [1,2,3] 라는 수열이 있을경우, 부분집합은

[1], [2], [3], [1,2], [1,3] [2,3] [1,2,3] 처럼 나올 것 이다.

 

[1,3]처럼 연속되지 않는 수열을 뽑아내려면 이중반복문 만으로는 충분치 않아보이는데... 흠..... 아래 그림으로 좀더 방법을 찾아보자.

 

위 그림처럼 진행이 가능하다면, 3개의 원소가 있는 array 에서는 모든 부분수열을 찾을수 있다. 항상 저 나무를 그리면 DFS/BFS 가 먼저 생각나긴 하는데....흠.... 아무튼, 위 그림을 한 배열에서 구현하기 위해서 아래 그림처럼 생각해 보았다.

인덱스가 n 일때, 다음 턴으로 넘어갈 경우, n 까지 구한 부분수열의 합을 제외하고 넘겨주느냐, 포함하고 넘겨주느냐로 위의 트리를 구현할 수 있다.

즉, 재귀 함수를 통해 sum을 넘겨주느냐, sum-arr[n]을 넘겨주느냐로 구현이 가능하다.

 

<소스코드>

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> arr;
int res = 0;
int n = 0;
int s = 0;
int cnt = 0;
 
void cur(int ind, int sum) {
 
    if (ind >= n) return;
    sum += arr[ind];
    if (sum == s) 
        cnt++;
    
    cur(ind + 1, sum);
    cur(ind + 1, sum - arr[ind]);
}
 
int main() {
    int temp;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        arr.push_back(temp);
    }
    cur(0, 0);
    cout << cnt;
}

 

문제 :

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

1182번: 부분수열의 합