글 읽기 - 도대체 어디에서 시간초과가 나는건가요?

shinbian11 4년 전 0

항상 시간초과가 납니다..9%에서 항상 시간초과가 나는데 어떤걸 줄어야 하나요? 정확히 알려주세요 ㅠㅠ 진짜 못찾겠습니다...

visual studio에서 돌렸을때는 답이 바로바로 나오던데 여기서 시간초과가 나는 이유는 뭔가요?

#include <stdio.h>
#include <math.h>
int arr[1230] = { 0 };
int gold_1[1230] = { 0 };
int gold_2[1230] = { 0 };
int gold_sub[1230] = { 0 };

void partition(int num)
{
	int goldbach = 0;
	for (int i = 0; arr[i] != 0; i++)
	{
		for (int j = 0; arr[j] != 0; j++)
		{
			int rest = num - arr[i];
			if (rest == arr[j]) //arr[i]+arr[j] == num일때 그 arr[i]와 arr[j]를 골드바흐 배열에 저장한다.
			{
				gold_1[goldbach] = arr[i];
				gold_2[goldbach] = arr[j];
				goldbach++;
			}
		}
	}
	if (goldbach == 2) //골드바흐 파티션이 1개라면, goldbach는 2가 나옴
		printf("%d %d\n", gold_1[0], gold_2[0]);
	else //골드바흐 파티션이 2개이상이라면, goldbach는 2가 아님!
	{
		int min = 10000;
		int index = 0;
		for (int i = 0; gold_1[i] != 0; i++) //두 소수의 차이를 구해서 가장 작은 차이가 나는 파티션을 출력
		{
			if (gold_1[i] >= gold_2[i])
				gold_sub[i] = gold_1[i] - gold_2[i]; //gold_sub : 두 소수의 차이
			else
				gold_sub[i] = gold_2[i] - gold_1[i];
			if (min > gold_sub[i]) //두 소수의 차이가 가장 작은 것의 index를 찾아서
			{
				min = gold_sub[i];
				index = i;
			}

		}
		printf("%d %d\n", gold_1[index], gold_2[index]);// 그 index에 해당하는 소수를 출력!
	}

}
int main()
{
	int testcase;
	scanf("%d", &testcase);
	int idx = 0;
	for (int i = 2; i < 10000; i++) //소수 구해서 arr배열에 넣어놓기
	{
		int flag = 1;
		for (int j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
				flag = -1;
		}
		if (flag == 1)
		{
			arr[idx] = i;
			idx++;
		}
	}

	for (int i = 0; i < testcase; i++) //testcase번 입력 받는다.
	{
		int num;
		scanf("%d", &num);
		partition(num); //입력 받은 수의 골드바흐 파티션 구하기!

	}
}