반갑습니다!

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

알고리즘 문제 풀이

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

김덜덜이 2020. 4. 17. 01:49
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
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]);
    }
}

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 17822 원판 돌리기  (0) 2020.04.18
[프로그래머스] 방문 길이  (0) 2020.04.17
[프로그래머스] N개의 최소공배수  (0) 2020.04.17
[백준] 1806 부분합  (0) 2020.04.17
[백준] 2003 수들의 합 2  (0) 2020.04.17