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

코딩테스트 연습 - 소수 만들기 | 프로그래머스 (programmers.co.kr)

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

---

🔎 문제 설명

숫자 세개를 더해서 소수가 되는 경우의 개수를 구하려고 함.

num이라는 배열에 숫자들이 주어지고 서로 다른 3개를 골라 더해 소수가 되는 경우의 수를 리턴

 

🔎 풀이 과정

소수가 되는 조건 = 1과 자기 자신 이외의 숫자로 나누어지지 않는다.

 

모든 경우의 수를 다 따져봐야 되므로 완전 탐색으로 풀어야 할 거같다.

반복문을 돌려서 서로다른 3개를 더할 수있게하고, 더해진 숫자를 n 변수에 저장. 

>> 조합으로 짜면 된다. (반복문 3개를 돌림)

 

그리고 2~n-1까지 나눠지는게 있는지 확인 나눠지면(나머지가 0이면) 소수가 아님.

그래서 안나눠진다면 answer에 1을 더해줌.

 

 

<정답 코드>

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

int isdecimal(int x) {
    for (int i = 2; i < x; i++) {
        if (x % i == 0) return 0;
        else continue;
    }
    return 1;
}

int solution(vector<int> nums) {
    int answer = 0;
    int n;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            for (int k = j + 1; k < nums.size(); k++) {
                n = nums[i] + nums[j] + nums[k];
                answer += isdecimal(n);
            }
        }
    }
    return answer;
}

 

 

<개념> 배열/벡터로 주어진 숫자들의 조합(nCr) 구하기

조합하려는 수(r)만큼 반복문을 돌려주면 된다.

//만약 r=3일때 
for(let i=0; i<arr.length; i++){
    for(let j=i+1; j<arr.length; j++){
        for(let k=j+1; k<arr.length; k++) {
            ans.push([ arr[i], arr[j], arr[k] ]);
        }
    }
}