[BoJ] #1182 부분 수열의 합 / c++

 

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

1182번: 부분수열의 합

 

부분수열의 합

2 초

256 MB

 

문제

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

입력

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

출력

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

 

---

IDEA

부분 수열을 구하는 것이 핵심이다.

무작위로 임의의 n개 원소를 꺼내서 (=조합) 부분 수열을 어떻게 만들어야 할까?

 

 

SOLUTION

원소들을 하나씩 돌면서 해당 원소를 현재 부분 수열에 포함시키는 경우 / 포함시키지 않는 경우로 나누고,

각각의 상황마다 재귀함수롤 호출한다. 재귀함수는 문제에서 요구하는 조건을 만족하면 종료한다.

 

 

CODE

#include <iostream>

using namespace std;

int N, S;
int answer = 0;
int arr[20];

void recur(int idx, int currentSum) {
    if(idx == N) return;

    currentSum += arr[idx];
    if(currentSum == S) answer++;

    recur(idx+1, currentSum);			// 현재 원소 포함하는 경우
    recur(idx+1, currentSum - arr[idx]);	// 현재 원소 포함시키지 않는 경우
}

int main() {

    cin >> N >> S;

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

    recur(0, 0);
    cout << answer;

    return 0;
}