14225 부분수열의 합

부분 수열의 합. 완전탐색의 정석적인 문제

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

1. 문제

---

간단 설명

수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램

첫째 줄에 수열 S의 크기 N (1 ≤ N ≤ 20)

둘째 줄에는 수열 S (1 <= S <= 100,000)가 주어진다

2. 문제 분석

---

필요변수

수열 S의 원소 개수 N

수열 S를 저장할 arr_s

수가 조합이 가능한지를 저장해둘 배열 check

주의점

• 최대 나올수 있는 숫자는?

S의 각 원소는 최대 100,000까지 나올 수 있으므로,

즉 최대 100,000가 20번 나올 수 있음

100000 * 20까지 체크해야함 check[2,000,001]

• DFS를 돌릴때, 어떤 방식으로 접근할 것인지

알고리즘

1. N 입력받고, 수열 S채우기
2. 재귀함수를 이용해 숫자들을 이용한 합을 만들기
	2-1. 0번 원소부터 sum에 이 수를 더할지 말지 정함
	- 더한다면 다음 재귀함수를 호출할 때 sum에 이 수를 더하고
	- 더하지 않는다면 sum을 그대로 넘겨줌
	2-2. 이를 N개의 원소를 모두 둘러볼 때 까지 확인함
	2-3. N개의 레벨을 모두 둘러봤다면, 현재 저장된 sum값을 조합 가능하다고 check 배열에 표시해둠
3. [1,MAX] 사이의 수 중에서 체크가 되지 않은 수를 찾아 출력 후 종료

3. 소스코드

---

#include <iostream>

using namespace std;

#define MAX 20000001

int N;
int arr_s[21];

bool check[MAX];

void recursive(int level, int sum) {
	if (sum > MAX) { return; }
	if (level == N) {
		check[sum] = true;
		return;
	}

	recursive(level + 1, sum + arr_s[level]);
	recursive(level + 1, sum);
}

int main() {
    // 1. 입력받기
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N; 
	for (int i = 0; i < N; i++) {
		cin >> arr_s[i];
	}
    // 2. 재귀함수 돌리기
	recursive(0, 0);
    // 3. 만들 수 없는 수 찾아 출력
	for (int i = 1; i < MAX; i++) {
		if (check[i] == false) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}

추가

---

#include <iostream>

#define MAX 20000001

using namespace std;

int N;
int S[21];
bool number[MAX];

void run(int level, int sum) {
	if (level == N) {
		number[sum] = true;
		return;
	}

	run(level + 1, sum);
	run(level + 1, sum + S[level]);
}

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S[i];
	}

	run(0, 0);

	for (int i = 1; i <= MAX; i++) {
		if (number[i]) continue;
		cout << i;
		break;
	}

	return 0;
}