1182번: 부분수열의 합 (BOJ C/C++)

1182번: 부분수열의 합

사용 언어: C++

 

문제

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

입력

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

출력

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

 

풀이 1

부분수열의 합이 s인지 확인해야하므로 조합을 사용하는 문제라고 생각할 수 있다. n 또한 충분히 작으므로 백트래킹으로 풀 수 있으므로 재귀와 next_permutation을 사용해서 풀 수 있다. 풀이 1은 재귀를 사용한 풀이다.

#include <bits/stdc++.h>
using namespace std;

int N, S;
int arr[20];
int cnt;

void func(int cur, int sum){
    if(cur == N) return;
    if(sum + arr[cur] == S) cnt++;

    func(cur+1, sum);
    func(cur+1, sum + arr[cur]);
}

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

    cin >> N >> S;

    for(int i=0; i<N; i++)
        cin >> arr[i];

    func(0, 0);
    cout << cnt << '\n';

    return 0;
}

 

풀이 2

재귀가 아닌 next_permutation을 사용한 풀이.

#include <bits/stdc++.h>
using namespace std;

int n, s, arr[20], sum, cnt;
bool isused[20];

int main(void){
    cin >> n >> s;
    for(int i=0; i<n; i++)
        cin >> arr[i];
    for(int i=0; i<20; i++)
        isused[i] = 1; //1 : 사용X, 0: 사용
    for(int i=0; i<n; i++){
        isused[i] = 0; //사용
        do{
            sum = 0;
            for(int j=0; j<n; j++)
                if(!isused[j]) //사용하는 것만 더하기
                    sum += arr[j];
            if(sum == s) cnt++;
        }while(next_permutation(isused, isused + n));
    }
    cout << cnt << '\n';

    return 0;
}