https://programmers.co.kr/learn/courses/30/lessons/12977
에라토스테네스의 체를 만들고, 순열을 통해 주어진 숫자중 3개를 뽑아 그 세 수의 합이 소수인지 파악하면 된다.
#include <vector>
#include <algorithm>
#define LEN 50001
using namespace std;
bool seive[LEN];
void set_seive () {
fill(seive, seive + LEN, true);
seive[0] = seive[1] = false;
for(int i = 2; i < LEN; i++) {
if (seive[i]) {
for (int j = 2; i * j < LEN; j++) seive[i * j] = false;
}
}
}
int solution(vector<int> nums) {
int answer = 0;
int is_prime;
vector<bool> comb(nums.size());
comb[0] = comb[1] = comb[2] = true;
set_seive();
do {
is_prime = 0;
for (int i = 0; i < comb.size(); ++i) {
if (comb[i]) is_prime += nums[i];
}
if (seive[is_prime]) answer++;
} while (prev_permutation(comb.begin(), comb.end()));
return answer;
}
'coding_test > programmers' 카테고리의 다른 글
lv1 / 키패드 누르기 / 카카오 기출 / C++ (0) | 2022.07.13 |
---|---|
lv2 / 문자열 압축 / 카카오 기출 / C++ (0) | 2022.07.13 |
lv1 / 신고 결과 받기 / 카카오 기출 / C++, Python (0) | 2022.06.29 |
lv1 / 최대공약수와 최소공배수 / C++ (0) | 2022.02.06 |
lv1 / 제일 작은 수 제거하기 / C++ (0) | 2022.02.06 |