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

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

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

 문제

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

 

 입력

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

 

 

 출력

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

 

 

 풀이

#include <iostream>
#include <vector>
using namespace std;

int N, S;
vector<int> temp;
int result = 0;

void ff(int idx, int sum){
	if(idx == temp.size()){
		if(sum == S) result++;
		return;
	}
	
	ff(idx + 1, sum);
	ff(idx + 1, sum + temp[idx]);
}

int main() {
	cin >> N >> S;
	
	for(int i=0;i<N;i++){
		int k;
		cin >> k;
		temp.push_back(k);
	}
	
	ff(0, 0);
	if(S==0) result--;
	cout << result;
	return 0;
}

 알고리즘 문제를 풀면서 기본적으로 할 줄 알아야 하는 개념이라고 생각하는 문제이다. 순열 조합과 같은 문제인데 백준에 있는 N과 M 시리즈를 풀어보면 도움이 많이 된다. 이 문제는 처음에 연속적인 부분수열의 합 문제인줄 알았는데 그냥 부분수열의 합이었고 N의 크기도 20밖에 안돼서 브루트 포스로 문제를 풀었다. 각 원소별로 더하거나 더하지않거나의 두가지 경우로 나뉘기 때문에 시간복잡도는 O(2^N) 이다. N의 크기가 작기 때문에 쉽게 풀렸다.

 첫번째 시도에서 틀렸습니다를 받았는데 이유는 S가 0일 때는 result에서 1을 빼줘야한다. sum의 초기값이 0으로 시작하고 문제에서 크기가 양수인 부분수열을 말하고 있기 때문이다.

 

위 코드에서 ff 함수의 형식을 외워두는 것도 문제풀이에 크게 도움이 되는 것 같다.