백준 1182 - 부분수열의 합

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

1182번: 부분수열의 합

문제 설명

---

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

 

 

접근 방식

---

처음부터 하나씩 더해가면서 합의 모든 경우의 수를 구하면서 합이 같은 경우 카운트를 증가시킨다. 완탐 또는 Broute force를 이용한다.

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n,s;
int cnt=0;
int arr[21];
void bf(int start,int sum){
    for(int i=start+1;i<n;i++){
        int temp_sum=0;
        temp_sum=sum+arr[i];
        //합의 다음 항목을 더하기 전에 주어진 합과 같으면 카운트 증가
        if(temp_sum==s)cnt++;
        //각각의 모든 경우의 합을 완탐으로 계산한다.
        bf(i,temp_sum);
    }

}
int main(){
    cin>>n>>s; 
    for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<n;i++){
        //합이 주어진 합의 수와 같으면 카운트 증가
        if(arr[i]==s)cnt++;
        bf(i,arr[i]);
    }
    cout<<cnt<<"\n";
    return 0;
}

funny algorithm *0* ~