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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWaJ3q8qV-4DFAUQ&categoryId=AWaJ3q8qV-4DFAUQ&categoryType=CODE

SW Expert Academy

dfs를 이용해 세 소수의 합이 N과 같은 경우의 수를 구하도록 한다.

우선 소수를 판별하기 위해 bool형 벡터 prime에 에라토스테레스의 체를 활용한

 

소수인 수들을 false로 둔다.

(소수 관련 글은 아래 링크..!)

eunchanee.tistory.com/18

(프로그래머스 c++)소수 찾기

dfs를 호출하여 찾도록 한다.

우선 탈출 조건으로 현재 합이 N을 넘는지, 세 수를 더했는지 확인을 해준다.

만약 현재 합이 N과 같고, count가 3이면 ans++을 해주도록 한다.

 

아니라면 for문을 통해 소수를 더해주도록 한다.

중복이 가능하기 때문에 start 변수로 소수의 시작 부분을 지정해주도록 한다.

현재의 합 + p[i]가 N보다 작다면 dfs를 호출하여 계속 파고들도록 한다.

count나 합을 계속 더해나가면서 탐색을 하면 된다..!

#include <iostream>
#include <vector>

using namespace std;

int N = 0;
int ans = 0;
vector<bool> prime(1000, false);
vector<int> p;

void dfs(int current, int count, int start)
{
    if(current >= N || count >= 3)
    {
        if(current == N && count == 3)
            ans++;
        return;
    }
    for(int i = start; i < p.size(); i++)
    {
        if(current + p[i] <= N)
            dfs(current + p[i], count + 1, i);
        else
            return;
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    for(int i = 2; i <= 999; i++)
    {
        if(!prime[i])
        {
            p.push_back(i);
            for(int j = i + i; j <= 999; j += i)
                prime[j] = true;
        }
    }
    
    for(int tc = 1; tc <= t; tc++)
    {
        ans = 0;
        cin >> N;
        
        dfs(0, 0, 0);
        
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}