가능한 시험 점수

이문제 처음 DFS로 풀었는데 시간초과 뜬다.

#include<set>
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;

int iLast;
set<int>sCon;
vector<int> vScore;

void dfs(int start, int depth)
{
    if (depth == iLast)
    {
        sCon.insert(start);
        return;
    }
    dfs(start + vScore[depth], depth + 1);//더해주는경우
    dfs(start, depth + 1);//안더하고 0으로 처리해버리는 경우
}



int main() 
{
    int testcase(0); cin >> testcase;
    for (int m = 0; m < testcase; m++)
    {
        vScore.clear();
        int iSize; cin >> iSize;
        iLast = iSize;

        for (int i = 0; i < iSize; i++)
        {
            int iTemp; cin >> iTemp;
            vScore.emplace_back(iTemp);
        }

        dfs(vScore[0], 1);//0아닌경우
        dfs(0, 1);//0인경우

        cout << "#" << m + 1 << " " << sCon.size() << endl;
    }
}

두번째는 dfs말고(인터넷참조)

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int N;
int score[100];
bool visited[10001];
vector<int> canScore;
int answer;

int main() {

    int test_case;
    int T;

    cin >> T;

    for (test_case = 1; test_case <= T; test_case++) {

        //초기화
        N = 0;
        memset(score, 0, sizeof(score));
        memset(visited, false, sizeof(visited));
        canScore.clear();
        answer = 0;

        //입력
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> score[i];
        }

   
        //해법
        //0점부터 시작
        canScore.push_back(0);
        visited[0] = true;

        for (int i = 0; i < N; i++)
        {
            int iSize = canScore.size();
            for (int j = 0; j < iSize; j++)
            {
                int newScore = score[i] + canScore[i];

                if (!visited[newScore])
                {
                    canScore.emplace_back(newScore);
                    visited[newScore] = true;
                }
            }

        }

        //결과 갱신
        answer = canScore.size();

        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }

    //종료
    return 0;
}

    for (int i = 0; i < N; i++)
    {
        int iSize = canScore.size();
        for (int j = 0; j < iSize; j++)
        {
            int newScore = score[i] + canScore[i];

            if (!visited[newScore])
            {
                canScore.emplace_back(newScore);
                visited[newScore] = true;
            }
        }

    }

이부분 새롭게 추가하는 방식 논리적으로 이해하기