Level 1 소수 만들기

시간 복잡도: O(n^2*(n sqrt(x))), x = 숫자 3개의 합 => O(n^3)

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> nums) {
5  int answer = 0;
6
7  for(int i=0; i<nums.size()-2; ++i) {
8    for(int j=i+1; j<nums.size()-1; ++j) {
9      for(int k=j+1; k<nums.size(); ++k) {
10        int s = nums[i]+nums[j]+nums[k];
11        int t = sqrt(s);
12        
13        for(int m=2; m<=t; ++m) {
14          if(s%m == 0) {
15            s = 51;
16            break;
17          }
18        }
19        if(s!=51) ++answer;
20      }
21    }
22  }
23
24  return answer;
25}

입력 최대 개수가 50이하이기 때문에 브루트포스를 사용해도 시간은 충분하다.