swea 3752. 가능한 시험 점수

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

SW Expert Academy

[풀이]

처음엔 set을 써서 dfs로 조합을 구하는 방식으로 풀려고 했지만 시간 초과가 떴다.

그래서 for문만 써서 아직 나오지 않은 점수만 vector에 넣는 방식으로 풀었다.

 

#include <iostream>
#include <vector>
#include <cstring>//memset
using namespace std;

bool check[10001];
int T, N;
vector<int>score;

void solution() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(check, false, sizeof(check));
		cin >> N;
		score.push_back(0);
		check[0] = true;
		int s;
		for (int i = 0; i < N; i++) {
			cin >> s;//배점
			int sSize = score.size();
			for (int j = 0; j < sSize; j++) {
				int newScore = score[j] + s;//새롭게 더해진 점수
				//해당 점수가 이미 있으면 
				if (check[newScore])
					continue;
				score.push_back(newScore);
				check[newScore] = true;
			}
		}
		cout << '#' << t << ' ' << score.size() << '\n';
		score.clear();
	}
}

int main() {
	solution();
	return 0;
}