[Java] BOJ2023, 백준 - 신기한 소수

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

2023번: 신기한 소수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	4 MB	5372	2535	1929	46.281%

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

 

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

 

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

 

 

<풀이>

문제 그대로 소수일 때 한자리씩 추가해가면서 새 숫자도 소수인지 판단해주려고 했다.

문제에서 특별히 고려해야 할 점은 아래 두 가지밖에 없다.

1. 시작하는 수는 2,3,5,7만 가능하다.
2. 짝수는 붙이지 않는다. 짝수는 무조건 소수가 아니기 때문

알고리즘은 꽤나 쉬운 편.

관건은 시간과 메모리인데, 가능할지 계산해보도록 하자.

 

시간복잡도

1. 소수 판별

10^8이면 1억인데, 시간 제한은 2초이다. 보통 1억당 1초로 계산하니, 2억까지라고 생각하자.

1부터 1억까지 소수인지 판단할건데, 에라토스테네스의 체 알고리즘을 이용할것이다.

에라토스테네스의 체는 O(log(logN))의 시간복잡도가 소요된다고 한다.

총 1억가지의 경우의 수로 계산해보면 O(log(logN))=약 9천만

입력 범위 내의 모든 숫자가 소수인지 검사하더라도 시간은 충분하다.

 

2. 자릿수 더하기

이제 숫자를 붙여가면서 얼마나 나올지 계산해보자.

처음에 제시한 조건에 따라서 첫 번째 자리수는 4, 앞으로 붙일 수 있는 자릿수는 5

최대인 8자릿수로 가정하면

4*5^7=약 30만

엄청 적다.

 

만약 아무런 조건이 없는 상태라면 총 8자리, 들어갈 수 있는 숫자 10개로 10^8=1억가지 경우의 수가 존재한다.

차이가 엄청나군

 

메모리

이 문제는 메모리가 4MB밖에 주어지지 않기 때문에 메모리 제한을 잘 고려해야한다.

처음에는 모든 숫자가 소수인지 저장할 boolean타입의 배열을 만들어서 배열과 비교해주려고 했는데,,,

N=8, 1억까지의 수가 있다고 가정하면,,, 배열에 모든 수를 저장하면 메모리 초과가 일어난다.

따라서 배열에 저장해서 풀면 안됨!!

어차피 에라토스테네스의 체를 이용해서 전부 소수인지 판단해도 시간이 충분하니,

메소드를 이용하여 배열을 사용하지 않고 매번 숫자마다 소수인지 판단해주도록 하였다.

 

소스코드

import java.io.*;

public class Main {
	private static int n;
	private static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 입력부
		n = Integer.parseInt(br.readLine());

		// 10^8 = 1억
		// 자리마다 비교해도 시간초과 X
		go("2");
		go("3");
		go("5");
		go("7");
		System.out.println(sb);
	}

	private static void go(String num) {
		if (!prime(num))
			return;
		// 완료조건: N자리 수 소수 찾음
		if (num.length() >= n) {
			sb.append(num + "\n");
			return;
		}

		// 자리마다 비교
		// 홀수만 가능
		for (int i = 1; i < 10; i += 2) {
			go(num + i);
		}
	}

	// 에라토스테네스의 체: Nlog(log(N))
	// 소수인지 전부 다 찾아도 시간초과가 안되니,
	// 해당할 때마다 소수인지 검사를 해보자
	private static boolean prime(String num) {
		int number = Integer.parseInt(num);
		if (number == 0 || number == 1)
			return false;
		for (int i = 2; i * i <= number; i++) {
			if (number % i == 0) {
				return false;
			}
		}
		return true;
	}
}