[C++] 프로그래머스 : 소수 만들기 (LvL 1)

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

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

---

문제 풀이

 입력받은 값들 중 3개만 뽑아서 더해서 소수인지 따지고 소수가 맞다면 리턴할 값에 1을 더한다.

isPrime로 소수를 따지는데 1 이하의 경우는 제외하고, 2 이상의 숫자만 따진다. 어떤 숫자의 루트 값은 중간값이 되기 때문에 2부터 √N만 따져도 이후 값은 확인할 필요가 없기 때문에 i × i <= n까지만 따진다. (시간복잡도 O(√N))

느낀 점

 너무 쉬운 문제라 풀이가 필요할까 고민했다. 입력받는 값이 50개가 아니라 정말 많았다면 시간복잡도를 줄이기 위해서 더 나은 코드를 구현했겠지만 너무 쉬워서 고민하지 않았다.

코드

#include <iostream>
#include <vector>

using namespace std;
vector<int>v;

bool isPrime(int n) {
	if (n <= 1) return false;
	for (int i = 2; i * i <= n;i++) {
		if (n % i == 0) return false;
	}
	return true;
}

int solution(vector<int> v) {
	int ans = 0;
	for (int i = 0; i < v.size() - 2;i++) {
		for (int j = i + 1;j < v.size() - 1;j++) {
			for (int k = j + 1;k < v.size();k++) {
				if (isPrime(v[i] + v[j] + v[k])) ans++;
			}
		}
	}
	return ans;
}

int main() {
	int n, num;
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> num;
		v.push_back(num);
	}
	int ans = solution(v);
	cout << ans;
}