[백준] 1182번 부분 수열의 합

문제 링크 : https://www.acmicpc.net/problem/1182

문제

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

입력

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

출력

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

문제 이해

N개의 정수로 이루어진 수열이 들어오고, 이것들을 조합하여 S가 되는 경우의 수를 구하는 문제이다. 조합 문제이다.

문제 접근

1. 입력을 받는다.
2. 수열의 모든 조합을 더한다.
3. 더한 값과 S와 비교한다.'

dfs로 현재의 값이 더해진 값과 더하진 않을 값으로 나눠서 구현을 한다. 그러면, 모든 부분 수열의 합을 구할 수 있다. 그리고 함수가 실행할 때마다 S값과 비교하여 개수를 구해준다.

코드 구현(c++)

#include <iostream>
#include <vector>

using namespace std;

int N, S;
vector<int> nums;
bool check[21] = {false,};
int result = 0;

void dfs(int i, int sum){
    if(i == N) return;
    if(sum + nums[i] == S) result++;

    dfs(i+1 , sum);
    dfs(i+1, sum + nums[i]);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

     
    cin >> N >> S;
    int temp;
    for(int i = 0 ; i < N ; i++){
        cin >> temp;
        nums.push_back(temp);

    }
    dfs(0,0);
    cout << result;
}

평가

처음에 전과 동일한 문제라고 생각해, 동일한 방식으로 count의 범위만 늘려줘서 문제를 풀었다. 하지만 결과는 틀렸다고 나왔다. 매우 당황스러워 여러 군데를 보았지만, 문제점을 찾지 못했다,,, 그래서 여러 블로그를 찾아 다음과 같이 푸는 방법이 있다는 것을 알고 다시 풀었다. 여전히 부족하다. dfs와 bfs도 다시 정리해야겠다.