C# 백준 9020번 골드바흐의 추측

문제

using System;
using System.Text;
using System.Collections.Generic;
namespace _6
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int T = Convert.ToInt32(Console.ReadLine());
            for (int K = 0; K < T; K++)
            {
                int input = Convert.ToInt32(Console.ReadLine());
                int first = 0;
                int second = 0;
                int firstSave = 0;
                int secondSave = 0;
                int difference = 10000;
                List<int> deArray = decimalArray(input);
                for (int i = 0; i < deArray.Count; i++)
                {
                    first = deArray[i];
                    if (deArray.Contains(input - deArray[i]) && input - deArray[i] >= first)
                    {
                        second = input - deArray[i];
                        if (difference > (second - first))
                        {
                            difference = second - first;
                            firstSave = first;
                            secondSave = second;
                        }
                    }
                }
                Console.WriteLine(firstSave + " " + secondSave);
            }
        }
        public static List<int> decimalArray(int input)
        {
            List<int> result = new List<int>();
            for (int i = 1; i <= input; i++)
            {

                if (i == 1)
                    continue;
                if (i == 2 | i == 3)
                    result.Add(i);

                double sqrt = Math.Truncate(Math.Sqrt(i));
                //제곱근 이하의 수에서 나누어 떨어지지 않으면 소수이므로 제곱근의 버림값을 저장
                for (int j = 2; j <= sqrt; j++)
                {
                    if (i % j == 0)
                    {
                        break;
                    }
                    else
                    {
                        if (j == sqrt)
                        {
                            result.Add(i);
                        }
                    }
                }
            }

            return result;
        }

    }
}

소수 구하기의 코드를 변형해서 푼것이다.

1. 값이 Input으로 들어오면 input값 이하의 모든 소수를 List에 저장한다.

2. 리스트의 첫번째 값을 first의 대입하여 input-first 역시 소수일경우 firstSave와 secondSave에 저장한다.

3. 2와 같은 방식으로 리스트 내의 모든 소수를 확인해보고 차이값이 가장 적은 것을 저장하면 된다.

여기서 시간초과가 뜨지 않게끔 하는 포인트는 4번에 있다.

4. 소수는 리스트의 절반까지만 확인해본다.

예를 들어 16이 input으로 들어오면 소수 리스트는  2 3 5 7 11 13이 될것이다. 만약 4번 제약이 없을경우 만들어 질수 있는 조합은

[3 13], [5 11], [11 5], [13 3] 이다. 이때 뒤에 두가지는 앞에서 이미 체크했기 때문에 4번과 같은 제약이 생긴다.