🖊️ 문제

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

🖊️ 풀이

n이 최대 50개..?
그냥 냅다 삼중포문 돌려도 되겠다
근데 합이 3000까지 가능하니
소수 판별에서 시간복잡도를 줄여야겠구나!

옛날에 했던,, O(sqrt(N))의 소수 판별 알고리즘으로 풀었는데
아니
잘만 나오는데 자꾸 틀렸다는거임!! ㅠㅠ
왜인지 몰랐는데

11 = 1 + 3 + 7
11 = 2 + 4 + 5
이거 두 개를 다른 케이스로 쳐줘야 했던 거다
암생각없이 unordered_set에 갖다박아서 틀려버렸다ㅜㅜ
이런..
테스트케이스를 잘 보자!!

🖊️ 코드

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

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

int solution(vector<int> nums) {
    int answer = 0;
    vector<int> vec;
    
    for (int i = 0 ; i < nums.size() - 2 ; i++) {
        for (int j = i+1 ; j < nums.size() - 1 ; j++) {
            for (int k = j+1 ; k < nums.size() ; k++) {
                int cnt = nums[i] + nums[j] + nums[k];
                vec.emplace_back(cnt);
            }
        }
    }
    
    for (auto& s : vec) {
        if (isSosu(s)) answer += 1;
    }

    return answer;
}