백준(1153번) - 네 개의 소수(Java) (수학)

import java.util.*;
import java.io.*;


public class Main
{
	static int n;
	static boolean[] prime;
	static boolean able;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		era();
		
		pick(0, 0, "");
		
		if(!able) System.out.println(-1);
		
	}
	public static void era()
	{
		prime = new boolean[n+1];
		
		prime[0] = prime[1] = true;
		
		for(int i = 2 ; i*i <= n ; i++)
		{
			if(!prime[i])
			{
				for(int j = i*i ; j <= n ; j += i) prime[j] = true;
			}
		}
	}
	
	public static void pick(int cnt, int value, String str)
	{
		if(cnt == 4 && value == n)
		{
			able = true;
			
			System.out.println(str);
			System.exit(0);
		}
		
		for(int i = 2 ; i <= n ; i++)
		{
			if(!prime[i] && value+i <= n)
			{
				pick(cnt+1, value+i, str+Integer.toString(i)+" ");
			}
		}
	}
}

 

 

 

import java.util.*;
import java.io.*;


public class Main
{
	static int n;
	static boolean able;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		pick(0, 0, "");
		
		if(!able) System.out.println(-1);
		
	}
	public static boolean isPrime(int num)	//1 이하는 돌려보내는 수고를 안 해도 됨
	{
		for(int i = 2 ; i*i <= num ; i++) if(num % i == 0) return false;
		
		return true;
	}
	
	public static void pick(int cnt, int value, String str)
	{
		if(cnt == 4 && value == n)
		{
			able = true;
			
			System.out.println(str);
			System.exit(0);
		}
		
		for(int i = 2 ; i <= n ; i++)	//어차피 2부터 볼거임
		{
			if(isPrime(i) && value+i <= n)
			{
				pick(cnt+1, value+i, str+Integer.toString(i)+" ");
			}
		}
	}
}

모두 메모리 초과로 통과되지 못한 코드들이다.

메모리가 128MB로 굉장히 빡빡한 편인 이유가 있었는데 일반적으로 for문을 돌면서 찾아내는 문제가 아닌

<골드바흐의 추측>을 이용하는 문제이다.

 

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

이 문제에서 설명하듯이 2보다 큰 모든 짝수들은 두 소수의 합으로 나타낼 수 있다는 개념이다.

 

이 추측을 기반으로 코드를 짜야 통과가 되는 문제이다.

1. 8 미만은 4개의 소수로 절대 나타낼 수 없다.

2. 8 이상 중 짝수면 2 두 개를 미리 부여해 나머지 두 개의 소수를 찾아준다.

3. 8 이상 중 홀수면 2와 3을 미리 부여해 홀수를 짝수로 만들고 나머지 두 개의 소수를 찾아준다.

 

<문제>

https://www.acmicpc.net/problem/1153

 

<소스코드>

import java.util.*;
import java.io.*;


public class Main
{
	static int n;
	static String ans;
	
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		if(n < 8) ans = "-1";
		else if(n >= 8 && n % 2 == 0)
		{
			ans = "2 2 ";
			pick(n-4);
		}
		else if(n >= 8 && n % 2 == 1)
		{
			ans = "2 3 ";
			pick(n-5);
		}
		
		System.out.println(ans);
		
	}
	public static boolean isPrime(int num)	//1 이하는 돌려보내는 수고를 안 해도 됨
	{
		for(int i = 2 ; i*i <= num ; i++) if(num % i == 0) return false;
		
		return true;
	}
	
	public static void pick(int sum)
	{
		for(int i = 2 ; i <= n ; i++)	//어차피 2부터 볼거임
		{
			if(isPrime(i) && isPrime(sum-i)) 
			{
				ans = ans+Integer.toString(i)+" "+Integer.toString(sum-i);
				break;
			}
		}
	}
}