백준 11502 세 개의 소수 문제 해답

https://www.acmicpc.net/problem/11502

11502번: 세 개의 소수 문제

소수찾기의 알고리즘은 기본적으로 에라토스테네스의 체를 많이 이용한다

에라토스테네스의 체를 처음 들어보셨으면 아래의 글에 들어가 ppt를 읽고오면 도움이 될 것이다

2020/02/28 - [알고리즘] - [소수 찾기]에라토스테네스의 체

[소수 찾기]에라토스테네스의 체

#include <iostream>		//11502 세 개의 소수 문제
#include <vector>
using namespace std;
vector<int> v;
#define MAX 1001
int c[MAX] = { 0, };
int vector_size;
void init();
void primeNumberSieve();
void fineSolution();
int main()
{
	init();
	primeNumberSieve();
	fineSolution();
	return 0;
}
void init()
{
	for (int i = 0; i < MAX; i++)
	{
		c[i] = i;						//배열의 원소값을 각 index로 초기화
	}
}
void primeNumberSieve()
{
	for (int i = 2; i < MAX; i++)		//2부터 시작해서 특정한 숫자의 배수들은 소수가 아니다
	{
		if (c[i] == NULL) continue;		//이미 소수가 아닌 걸로 판정된 숫자들은 그냥 지나가고
		for (int j = i + i; j < MAX; j += i) {		//판정되지 않았다면 그의 배수들을 소수가 아닌 숫자로 판정한다
			c[j] = NULL;
		}
	}
	for (int i = 2; i < MAX; i++) {					//판정되지 않은 숫자들(소수들)을 모두 출력한다
		if (c[i] != NULL) v.push_back(i);
	}
	vector_size = v.size();
}
void fineSolution()
{
	int input, Case;
	bool isResult = false;
	cin >> Case;
	while (Case != 0) {
		cin >> input;
		for (int i = 0; i < vector_size; i++) {
			for (int j = 0; j < vector_size; j++) {
				for (int k = 0; k < vector_size; k++) {
					if (v[i] + v[j] + v[k] == input) {
						cout << v[i] << " " << v[j] << " " << v[k] << endl;
						isResult = true;
						goto next;
					}
				}
			}
		}
	next:
		if (isResult == false) cout << "0";
		Case--;
		isResult = false;
	}
}

이 코드의 문제점 : 세 개의 소수를 세 개의 반복문으로 찾고 있다.

K가 1000 이하밖에 안돼서 런타임 시간이 오래안걸려서 상관없지만

만약 좀 더 큰 수였으면 런타임이 더욱 길어져서 문제를 못 풀수도 있다.