백준(BOJ) 14225번 부분수열의 합

문제 : https://www.acmicpc.net/problem/14225

14225번: 부분수열의 합

 

풀이 :

 

S의 최대 크기는 20 이고 한 숫자당 10만이하 이니 합에 최대값은 20 * 100000일것이다. 이  배열을 잡은 후에 

 

재귀호출을 통해서 각 부분 수열을 더하거나 지나치거나 하여 모든 경우의 수를 체크해주자. 그 후 

 

1부터 시작해서 값이 false라면 종료한다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	bool range[20 * 100000];
	int S[20];
	int N;
	void solve(int begin, int sum)
	{
	if (begin == N) {
	range[sum] = true;
	return;
	}
	solve(begin + 1, sum + S[begin]);
	solve(begin + 1, sum);
	}
	int main()
	{
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
	cin >> S[i];
	}
	solve(0, 0);
	int start = 0;
	while (1)
	{
	if (range[start] != 1) {
	cout << start << "\n";
	return 0;
	}
	start++;
	}
	}

view raw .cpp hosted with ❤ by GitHub