[Summer/Winter Coding(~2018)] 소수 만들기

참고 : programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

˙ nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
˙ nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

코드 풀이

소수 판별하는 알고리즘은 자주 쓰이므로 따로 외워두면 좋다.
먼저 nums 배열에 있는 숫자를 3개 선택해 합해서 소수인지 판별하는 문제이므로, 숫자 3개를 선택하기 위해 Combination 알고리즘을 활용했다. temp 배열의 앞 부분 3개의 숫자는 1로 채워두고 나머지 부분은 0으로 채워서 임시 조합을 생성했다. 그리고 do ~ while문으로 한 바퀴씩 돌 때마다 선택되는 3개의 숫자의 합이 소수인지 판별해서 소수가 맞다면 answer를 +1씩 하기로 한다. 

코드

#include <vector>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;


bool sosu(int n) {
	int k = (int)sqrt(n);

	for (int i = 2; i <= k; i++) {
		if (n % i == 0) 
			return false;
	}
	return true;
}


int solution(vector<int> nums) {
	
	int answer = 0;

	sort(nums.begin(), nums.end());

	vector<int> temp;

	for (int i = 0; i < 3; i++)
		temp.push_back(1);

	for (int i = 0; i < nums.size() - 3; i++)
		temp.push_back(0);

	sort(temp.begin(), temp.end());


	do {
		int sum = 0;
		for (int i = 0; i < temp.size(); i++) {
			
			if (temp[i] == 1)
				sum += nums[i];
		}

		if (sosu(sum) == true)
			answer++;

	} while (next_permutation(temp.begin(), temp.end()));

	return answer;
}

int main() {

	vector<int> nums = { 1, 2, 7, 6, 4 };

	cout << solution(nums);

	return 0;
}