[백준] 17103번: 골드바흐 파티션 [C#]

 

골드 바흐 파티션은 한 짝수 N을 구성하는 두 소수하고 한다.

주어지는 짝수들의 골드바흐 파티션의 개수를 구해서 출력하면 된다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int T = int.Parse(reader.ReadLine());
            int[] prime_box = new int[1_000_000]; // 소수의 개수를 예측할 수 없어서 임의의 크기를 지정해두었다
            int a = 0; // 소수일 시 하나씩 늘려가며 실제 소수의 개수를 파악한다
 
 
 
            for (int i = 2; i < 1_000_000; i++) // 최대 입력인 1_000_000 까지 소수를 판별해둔다
                if (is_Prime(i))
                    prime_box[a++] = i; // 실제 소수의 개수를 얻을 수 있다
 
 
            for (int j = 0; j < T; j++)
            {
                int input = int.Parse(reader.ReadLine());
 
                int count = 0; // 골드바흐 파티션의 개수를 세는 변수
                for (int k = 0; k < a; k++)
                {
                    if (prime_box[k] > input / 2) // 골드바흐 파티션을 중복해서 세는 경우를 방지
                        continue;
                    if (binarySearch(k, input, prime_box, a))
                        count++;
                }
                sb.Append(count + "\n");
            }
 
            print.WriteLine(sb);
 
        }
        static bool binarySearch(int k, int input, int[] prime_box, int a)
        {
            int low = 0;
            int high = a;
 
            while (high >= low)
            {
                int mid = (low + high) / 2;
                if (prime_box[k] + prime_box[mid] == input)
                    return true;
                else if (prime_box[k] + prime_box[mid] > input)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
 
            return false;
        }
 
        static bool is_Prime(int num) // 소수 판별 메서드
        {
            if (num % 2 == 0) // 2를 제외한 짝수는 모두 소수가 아니므로
                return num == 2;
 
            for (int i = 3; i <= Math.Sqrt(num); i+=2) // 소수 판별은 홀수로만 진행한다
            {
                if (num % i == 0)
                    return false;
            }
 
            return true;
        }
    }
}

 

주어질 짝수까지의 소수의 개수를 예측할 수 없어서 임의의 크기의 prime_box 배열을 만들어주었다.

이후 최대로 주어지는 입력인 1_000_000 까지 모든 소수를 판별해서 prime_box에 넣어주었고, 넣을 때마다 변수 a를 1씩 증가시켜 실제 소수의 개수를 파악해 두었다.

골드바흐 파티션의 개수를 세는건 이진 탐색을 이용하여, 시간을 절약해 주었다.

그런데, 예제의 입력 중 6은 서로 중복되는 숫자인 3과 3이 합쳐져 만들어지는 수라 별 이상이 없었지만,

100의 경우 41 - 59와 59 - 41처럼 골드바흐 파티션이 중복되어 카운팅 되는 문제가 있었다.

입력된 짝수의 중간을 기점으로 대칭되어 나타나기 때문에, 입력값의 절반까지만 판정을 진행해 주었다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int T = int.Parse(reader.ReadLine());
            List<int> prime_box = new List<int>();
            int max = 2;
 
            for (int a = 0; a < T; a++)
            {
                int num = int.Parse(reader.ReadLine());
                if (num > max)
                {
                    for (int i = max; i < num; i++)
                    {
                        if (is_prime(i))
                            prime_box.Add(i);
                    }
                    max = num;
 
                }
                int count = 0;
                for (int j = 0; j < prime_box.Count()-1; j++)
                {
                    if (prime_box[j] > num/2)
                        continue;
                    if (binary_search(prime_box, num, j))
                        count++;
                } sb.Append(count + "\n");
            }
            print.WriteLine(sb);
        }
 
        static bool binary_search(List<int> prime_box, int a, int j)
        {
            int low = 0;
            int high = prime_box.Count() -1;
 
            while (high >= low)
            {
                int mid = (low + high) / 2;
                if (prime_box[mid] + prime_box[j] == a)
                    return true;
                else if (prime_box[mid] + prime_box[j] > a)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            return false;
        }
 
        static bool is_prime(int input)
        {
            if (input % 2 == 0)
                return input == 2;
 
            for (int i = 3; i <= Math.Sqrt(input); i+=2)
            {
                if (input % i == 0)
                    return false;
            }
 
            return true;
        }
    }
}

 

소수의 개수를 예측할 수 없는 문제 때문에 배열에 너무나 큰 값을 줘버려, 메모리 낭비라고 생각이 들었다.

리스트는 검색 속도는 느리지만, 가변적으로 변하는 크기 덕분에 버려지는 공간이 없어서 이렇게 코드를 짜 보았다.

확실히 리스트를 사용하니 따로 소수의 크기를 저장해둘 변수를 쓸 필요가 없어져 더우 직관적으고 효율적인 코드가 된 것 같다.