백준 2023번 자바

문제

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

2023번: 신기한 소수

1. 접근 방법

- 왼쪽부터 한자리씩 늘려가며 소수인지 아닌지 확인을 한다.

- 해당 자리가 소수면 재귀를 통해 다음 자리수로 넘어간다.

- 자리수가 N과 동일해지면 값을 출력 후 탐색을 종료한다.

 

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main2023 {

	static int N;
	static int[] primeNums = {2,3,5,7};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		// 첫자리의 수는 2,3,5,7 중에서만 가능하다.
		for (int i=0; i<primeNums.length; i++) {
			StringBuilder sb = new StringBuilder();
			dfs(sb.append(primeNums[i]));
		}
	}
	
	public static void dfs(StringBuilder num) {
		if (num.length() == N) {
			System.out.println(num);
			return;
		}

		for (int i=1; i<10; i++) {
			int temp = Integer.parseInt(num.append(i).toString());
			boolean isPrime = true;
			
			for (int j=2; j<temp; j++) {
				if (temp%j == 0) {
					isPrime = false;
					break;
				}
			}
			
			if (isPrime) {
				dfs(num);
			}
            // 소수가 아닌 경우 다음 수를 추가하기 위해 이전 수를 제거해준다.
			num.deleteCharAt(num.length()-1);
		}
	}
}

 

정리 : 처음엔 소수여부 탐색에 시간초과가 날까 걱정했는데 다행히 정답이다. 하지만 구현을 해놓고보니 시간을 좀 더 단축시킬 수 있는 부분이 보인다. dfs메소드에서 내부for문의 범위를 temp / 2로 했어도 충분했을 것이다. 다음부터 소수를 구하는 문제에선 주의를 하자