Newer
Older
---
layout : wiki
title : SWEA 3752. 가능한 시험 점수
summary :
date : 2021-01-27 10:37:52 +0900
updated : 2021-12-15 18:09:02 +0900
tag :
public : true
published : true
parent : [[swea]]
latex : false
---
* TOC
{:toc}
- 수가 100개라서 부분 집합은 시간 초과날 거라고 생각함
- 모든 문제를 틀리는 경우인 0점이 반드시 포함되어야 함
- 0점을 vector에 삽입한다.
- 기존에 있는 vector의 각 데이터에 현재 문제의 배점을 더한 값을 vector에 추가한다.
- 한 번 방문했던 값은 다시 방문하지 않도록 방문 여부를 나타내는 visited 배열을 두었다.
- 계속 뒤로 삽입되어야 하므로 set을 사용하기에는 적절치 않다.
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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());
}
}
```