[프로그래머스] 소수 만들기

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

에라토스테네스의 체를 이용해서 소수를 미리 계산해두고 DFS를 사용하여 숫자 3개를 골라 해결하였다.

코드

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

int ans;
bool chk[3001];

void precalc() {
    fill(chk, chk + 3001, true);
    chk[0] = false;
    chk[1] = false;

    for (int i = 2; i * i <= 3000; i++) {
        if (!chk[i]) continue;
        for (int j = i * i; j <= 3000; j += i)
            chk[j] = false;
    }
}

void dfs(vector<int>& nums, int idx, int cnt, int sum) {
    if (cnt == 3) {
        if (chk[sum]) ans++;
        return;
    }

    for (int i = idx + 1; i < nums.size(); i++) {
        dfs(nums, i, cnt + 1, sum + nums[i]);
    }
}