[programmers] Lv.1 소수 만들기(c++)

바로 직전 소수 찾기 문제와 비슷하다.

이거나 저거나 비슷한 난이도 같은데 얘는 Lv.1이었다.

 

#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

bool is_prime(int num){
    if(num <= 1) return false;
    
    for(int i=2; i<=sqrt(num); i++){
        if(num%i == 0) return false;
    }
    
    return true;
}

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

    vector<int> pick(nums.size(), 0);
    for(int i=pick.size()-3; i<pick.size(); i++)
        pick[i] = 1;
    
    do{
        int sum = 0;
        for(int i=0; i<pick.size(); i++){
            if(pick[i] == 1) sum += nums[i];
        }
        
        if(is_prime(sum)) answer += 1;
    }while(next_permutation(pick.begin(), pick.end()));

    return answer;
}

---

문제

https://programmers.co.kr/learn/courses/30/lessons/12977

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

728x90

---

[접근1]

바로 직전 문제에서 만들었던 is_prime함수를 그대로 사용하였다.

bool is_prime(int num){
    if(num <= 1) return false;
    
    for(int i=2; i<=sqrt(num); i++){
        if(num%i == 0) return false;
    }
    
    return true;
}

---

[접근2]

숫자 3개를 골라야함

저번문제처럼 순서가 중요하거나 하진 않아서 무슨 숫자를 고를지만 고르기 위해 pick vector를 하나 만들었다.

맨 마지막에 111을 추가해서 이것을 permutation 돌리면 모든 경우의 수를 나타낼 수 있다.

vector<int> pick(nums.size(), 0);
for(int i=pick.size()-3; i<pick.size(); i++)
    pick[i] = 1;

do{
    ...
}while(next_permutation(pick.begin(), pick.end()));

---

[접근3]

pick이 고른(1) 숫자들을 sum에 더해서 is_prime함수에 넣어준다.

소수이면 answer을 1 증가시켜준다.

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

    if(is_prime(sum)) answer += 1;
}while(next_permutation(pick.begin(), pick.end()));