티스토리 뷰

반응형

 

소수 구하기를 생각하는 거 자체는 어렵지 않았는데 모든 수의 합을 어떻게 찾는지 좀 고민했던 문제

 


문제의 조건

 

1. 정수 배열이 하나 주어짐

 

2. 배열에서 숫자 3개를 뽑아서 더한 값이 소수이면 카운트 1증가

 

3. 주어진 배열에서 2번의 소수 카운트가 최대 몇 개 나오는지 구하기 

 


 

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

bool isPrimeNum(int num)
{
    if (2 > num)
        return false;

    //sqrt는 제곱근을 구해주는 함수
    //자세한 설명은 링크 글 참고 
    int a = static_cast<int>(sqrt(num));
    for (int i = 2; a >= i; i++)
    {
        if (0 == num % i)
            return false;
    }

    return true;
}

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

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

    for (int i = 0; nums.size() - 2 > i; i++)
    {
        for (int j = i+1; nums.size() - 1 > j; j++)
        {
            for (int k = j+1; nums.size() > k; k++)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if (isPrimeNum(sum))
                    answer++;
            }
        }
    }

    return answer;
}

 

 

https://notepad96.tistory.com/entry/C-%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84%ED%95%98%EA%B8%B0

 

C++ 소수 판별하기

  1. 소수 판별 소수란 1보다 크며 1 이외의 자신으로만 나누어지는 수이다. 어떠한 수 n이 소수인지 판별하기 위하여 for문을 사용하여서 2부터 나누어 n-1까지의 수 중 나머지가 0이 되는 수가 존

notepad96.tistory.com

 

소수 구하기와 sqrt 함수에 관해서 쉽게 설명해놓은 블로그 글이 있어 이걸 많이 참고했습니다. 

알고리즘 문제 풀면서 새로운 함수 많이 알게 되어서 좋네용~ㅋㅋ 

 

 

알고리즘 문제 풀 때 2중 for문도 시간초과 때문에 피하는 경우가 많다 보니 3중까지는 생각도 못 했었는데 

질문하기의 힌트 보고 해 봤는데 전부 통과되었습니다. 

다음부터는 첨부터 무서워하지 말고 일단 젤 기본적인 방법부터 해 보자...

반응형
댓글
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/01   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함