SWEA 5986. 새샘이와 세 소수 (C++)

#include <stdio.h>
#include <vector>

using namespace std;

int N, cnt;
bool primeNum[1000];
vector<int> v;

void Eratos(int n)
{
    for (int i = 2; i < n; i++)
    {
        primeNum[i] = true;
    }

    for (int i = 2; i < n; i++)
    {
        if (primeNum[i])
        {
            v.push_back(i);
            for (int j = i * i; j < n; j += i)
            {
                primeNum[j] = false;
            }
        }
    }
}

void solve(int depth, int start, int sum)
{
    if (depth == 3)
    {
        if (sum == N)
            cnt++;

        return;
    }

    for (int i = start; i < v.size(); i++)
    {   
        if (v[i] + sum <= N)
            solve(depth + 1, i, sum + v[i]);
        else
            break;
    }
}

int main()
{
    Eratos(1000);

    int tc = 0;
    scanf("%d", &tc);
    for (int t = 1; t <= tc; t++)
    {
        cnt = 0;
        scanf("%d", &N);
        
        solve(0, 0, 0);

        printf("#%d %d\n", t, cnt);
    }
    return 0;
}

1. 소수만 벡터에 저장(벡터에 저장하지 않고 primeNum을 이용해서 소수를 판별하면 제한시간 초과됨)

2. DFS를 이용해서 모든 경우의 수 확인

3. 끝!!