BOJ 14225 : 부분수열의 합

문제

---

 

문제 풀어보기

 

 

풀이

---

 

완전 탐색을 하는데 중복되는 계산을 줄여주는 방법을 선택합시다.

재귀 문을 보면 그냥 포문 돌면서 하나씩 다 더해보는 겁니다.

 

 

그런데 저기서 st 인자를 없애고 모두 처음부터 본다면 어마어마한 중복이 발생합니다.

예를 들어 1, 2, 3, 4의 인자가 있다면

st 인자없이 모두 처음부터 탐색을 하는 경우

 

 

이러한 순서로 탐색할 겁니다.

하지만 현재 선택한 인덱스보다

작은 인덱스를 선택하는 경우는 모두 중복 수열이 됩니다.

따라서 st 인자를 사용해서 이전 인덱스는 넘어가게 해 줍시다.

 

코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <cstring>


using namespace std;
#define safe(x,y) x>=8 || x<0 || y<0 || y>=8

int dx[] = { -1, 0, 1, 0};
int dy[] = { 0, 1, 0 , -1};
//위 오른쪽 아래 왼쪽

//int dx[] = { -1, 1, 1, -1 };
//int dy[] = { 1, 1, -1 , -1 };
// 대각선


int n;
bool check[20 * 100'000];
vector<int> v(20);

void dfs( int st, int sum, vector<bool> used) {
	// st 부터 시작하므로 이전 숫자를
	// 중복탐색하지 않는다.
	for (int index = st; index < n; index++) {
		// 사용한 숫자는 사용X
		if (used[index]) continue;
		used[index] = true;
		check[sum + v[index]] = true;
		dfs( index+1, sum + v[index], used);
		used[index] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	vector<bool> ch(n, false);
	dfs(0, 0, ch);

	for (int i = 1;; i++) {
		if (!check[i]) {
			cout << i << endl;
			break;
		}
	}

	return 0;
}