[백준/C++] 17103 골드바흐 파티션 (S2)

유형	난이도	완료일	링크	특이사항
정수론	실버2	23/03/20	https://www.acmicpc.net/problem/17103

 

 

틀린 코드

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{   
    cin.tie(NULL);    
    ios_base::sync_with_stdio(false);
   
    int t;
    cin >> t;
    
    int n;
   
    for(int i=0;i<t;i++)
    { 
        int cnt =0;
        cin >> n;
        
        if(n==2)
        {
            cout << 0<<"\\n";
            continue;
        }
        else if(n==4)
        {
            cout << 1 <<"\\n";
            continue;
        }
        
        int a, b;
        bool a_check = true, b_check = true;
        bool ok = true;
        
        for(int j=3; j<=n/2; j+=2)
        {
            a_check=true; b_check=true;
            ok =true;
            
            a = j; b = n - a;
            for(int k = 2; k<=sqrt(a); k++)
            {
                if(a%k==0)
                {
                    a_check = false;
                    ok=false;
                    break;
                }
            }
            if(ok)
            {
                for(int k = 2; k<=sqrt(b); k++)
                {
                    if(b%k == 0)
                    {
                        b_check = false;
                        break;
                    }
                }                 
                if(a_check&&b_check)
                {
                    cnt++;
                }           
            }
            

        } 
        cout << cnt <<"\\n";
    }
    
   
    
    return 0;
}

  대략 최대 반복 횟수가 50만 이하라고 생각해서 통과할 줄 알았으나 시간 초과를 받았다.

맞는 코드

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int a, b;
int cnt;
bool a_check = true, b_check = true;

int arr[1000001];
bool check = true;

int main()
{   
    cin.tie(NULL);    
    ios_base::sync_with_stdio(false);
   
    int t;
    cin >> t;
	
	for(int i=2; i <= sqrt(1000000); i++)
	{
		if(arr[i]==0)
		{
			for(int j = i ; j *i  <= 1000000; j++)
			{
				arr[j *i] = 1;
			}
		}
		
	}
		
	for(int i=0;i<t;i++)
    { 
        cnt = 0;
        cin >> n;
        
        if(n==2)
        {
            cout << 0<<"\\n";
            continue;
        }
        else if(n==4)
        {
            cout << 1 <<"\\n";
            continue;
        }
        
		for(int j = 3; j<=n/2; j+=2)
		{
			if(!arr[j] && !arr[n-j])
				cnt++;
		}		
        cout << cnt <<"\\n";
    }
    
   
    
    return 0;
}

  “에라토스테네스의 체” 라고 불리는 방식으로 코드를 짰다. 특정 수 이하의 소수들을 빠르게 구할 수 있는 알고리즘이다. 배열을 이용하여 n이 있다면 n이하의 수들의 배수를 지워가며 소수인 수들만 남기는 것이다.

우선 가능한 인풋 값 중 100만이 최대이므로 크기 100만의 배열을 만들어 소수들을 저장(표시)해놓고 인풋을 받을 때마다 확인하는 방식을 떠올리는게 첫번째고, 두 번째는 100만 이하의 소수들을 어떻게 빠르게 마킹할 것인지를 생각하는 것이었다.

이제 소수 자체에 관련해서는 시간을 최대로 절약할 수 있을 것 같다.