• 수가 100개라서 부분 집합은 시간 초과날 거라고 생각함
  • 모든 문제를 틀리는 경우인 0점이 반드시 포함되어야 함
    • 0점을 vector에 삽입한다.
  • 기존에 있는 vector의 각 데이터에 현재 문제의 배점을 더한 값을 vector에 추가한다.
  • 한 번 방문했던 값은 다시 방문하지 않도록 방문 여부를 나타내는 visited 배열을 두었다.
  • 계속 뒤로 삽입되어야 하므로 set을 사용하기에는 적절치 않다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <set>

using namespace std;

#define MAX_N 105

int N;
int tc;
bool visited[MAX_N * MAX_N];
int input[MAX_N];
vector<int> saved;

void init() {
	memset(visited, 0, sizeof(visited));
	saved.clear();

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &input[i]);
}

void solution() {
	saved.push_back(0);
	for (int i = 0; i < N; i++) {
		int cur = input[i];

		int savedSize = saved.size();
		for (int j = 0; j < savedSize; j++) {
			int next = cur + saved[j];
			if (visited[next]) continue;

			visited[next] = true;
			saved.push_back(next);
		}
	}
}

int main() {
	int testcase;
	scanf("%d", &testcase);
	for (tc = 1; tc <= testcase; tc++) {
		init();
		solution();
		printf("#%d %lu\n", tc, saved.size());
	}
}