3752. 가능한 시험 점수

문제

SW Expert Academy

영준이는 학생들의 시험을 위해 N개의 문제를 만들었다.
각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다.
학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까?

2
3
2 3 5
10
1 1 1 1 1 1 1 1 1 1

예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다
가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다.
두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 1점이다.
가능한 시험점수의 경우의 수를 살펴보면 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10으로 모두 11가지이다.

 

처음에 접근한 방법은 재귀함수였지만 n의 제한이 100이므로 시간초과가 나왔다.

2^100 -1 이기 때문이다.

 

두번째는 인터넷에서 영감을 얻었다.

무조건 0점은 들어가므로 벡터에 0을 넣고 배점을 입력받은 배열을 순회하면서 더해가는 것이다.

처음 벡터 {0}

+ arr[0]을 모든 벡터 요소에 더하기

두번째 백터 {0, 2}

+arr[1]을 모든 백터 요소에 더하기

세번째 백터 {0, 2, 3, 5}

. ..

그러기 위해서는 내가 가지고 있는 백터 요소와 현재 내가 더하려고 하는 값이 들어있는지 없는지 알아야 한다.

이는 bool chk[10001]로 체크했다.

cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        vector<int> v;
        v.push_back(0);
        chk[0] = true;

처음에 arr에 배점을 모두 넣고

v 백터를 만들어 초기 값으로 0을 넣는다.

당연히 0이 벡터에 들어갔으므로 chk[0]을 true로 만든다.

for (int i = 0; i < n; i++)
        {
            int k = v.size();
            for (int j = 0; j < k; j++)
            {
                if (chk[v[j] + arr[i]])
                    continue;
                chk[v[j] + arr[i]] = true;
                v.push_back(v[j] + arr[i]);
            }
        }

이제 arr 배열을 순회하면서 현재 들어가 있는 벡터 요소를 모두 더해주고, chk로 벡터에 들어갈 수 있는지 없는지 체크한다.

---

전체 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <cstring>
#include <set>
using namespace std;
int arr[101];
int n;
bool chk[10001];
void recur(int val, int idx);
int main()
{
    int t;
    cin >> t;
    int num = 1;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        vector<int> v;
        v.push_back(0);
        chk[0] = true;
        for (int i = 0; i < n; i++)
        {
            int k = v.size();
            for (int j = 0; j < k; j++)
            {
                if (chk[v[j] + arr[i]])
                    continue;
                chk[v[j] + arr[i]] = true;
                v.push_back(v[j] + arr[i]);
            }
        }

        cout << '#' << num << ' ' << v.size() << '\n';
        memset(chk, false, sizeof(chk));
        num++;
    }
    return 0;
}