글 읽기 - 시간초과 ㅠㅠ 어디서 줄여야할까요 ㅠ

tmdghks9574 5년 전 1

제곧내 입니다. ㅠㅠ 어디서줄이징.

#include<iostream>
using namespace std;

int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int a,k=0;
		cin >> a;
		int arr[a+1],ans[a];
		for (int i = 2; i <= a; i++)
			arr[i] = i;
		
		for (int i = 2; i <= a; i++) //소수찾기.
		{ 
			if (arr[i] == 0) 
				continue;
			for (int j = i + i; j <= a; j += i)
				arr[j] = 0;
		}
		
		for (int i = 2; i <= a; i++)  //검사
		{
			for(int j = i; j <= a; j++)
			{
				if (arr[i] + arr[j] == a) //차이 제일 적게출력할라고 저장
				{
					ans[k++] = arr[i];
					ans[k++] = arr[j];
				}
				else
					j++;
			}
		}
		cout << ans[k-2] << " " << ans[k-1] << '\n';
	}
}

djm03178 5년 전 1

소수는 테스트 케이스마다 변하지 않으므로 처음에 한 번만 구해두면 됩니다.
24, 26번째 줄처럼 이중 루프를 돌리지 않고 전체 리스트를 1번 이하로만 뒤져서 답을 찾을 수 있습니다.
cin과 cout이 번갈아서 나타나는 문제에는 cin.tie(NULL); 을 해주면 훨씬 빨라집니다.

tmdghks9574 5년 전 1

아항 감사합니다~

close852 5년 전 2

소수 x와 y의 합이 a입니다.

다르게 말하면 y = a-x입니다.

x만 구하고 a-x가 소수인 경우만 찾아서 비교하면 for문을 한번만 돌려도 풀 수가 있겠습니다.

arr[x]&& arr[a-x] 인케이스 이죠

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 ㅠㅠ 어디서 줄여야할까요 ㅠ

tmdghks9574 5년 전 1

djm03178 5년 전 1

tmdghks9574 5년 전 1

close852 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말