[SWEA] 3752. 가능한 시험 점수 - D4

---

문제

* 해당 문제의 모든 저작권은 SWEA 측에 있으며 본 블로그는 학업 흔적을 남겨 학업 상향을 위한 블로그로 이익을 추구하지 않으며 SWEA 측의 약관을 위배하지 않음을 명시합니다.*

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn 

SW Expert Academy

---

풀이

DP와 방문배열만 있으면 해결할 수 있는 간단한 문제이다.

숫자를 받고 그 숫자와 지금까지 벡터에 저장된 값을 더해보고 새로운 값이라면 벡터에 추가하면 된다.

---

소스 코드

#include <iostream>
#include <string>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <cctype>
#include <set>
#include <string.h>

// std::
using namespace std;

// 테스트 케이스
int T, test_case;

//사용할 변수
vector<int> v;
int dp[10001];

// 메인 함수
int main() {
	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/

	cin >> T;
	for (test_case = 1; test_case <= T; test_case++) {
		int N, size = 0, max = 0;
		memset(dp, 0, sizeof(dp));

		cin >> N;
		v.push_back(0);
		dp[0] = 1;

		for (int i = 0; i < N; i++) {
			int num, size = v.size();
			cin >> num;

			for (int n = 0; n < size; n++) {
				int sum = num + v[n];

				if (dp[sum] == 0) {
					dp[sum] = 1;
					v.push_back(sum);
				}
			}
		}

		cout << "#" << test_case << " " << v.size() << '\n';
		v.clear();
	}
}