[백준 골드 5] 2023번: 신기한 소수

문제

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

2023번: 신기한 소수

 

 

풀이

• N자리 숫자 중 왼쪽부터 1자리, 2자리, 3자리, ... N자리까지 모든 수가 소수가 되는 숫자를 모두 출력한다.
  ex) 7331 => 7, 73, 733, 7331 모두 소수이다.
• N은 1보다 크고 8보다 작다. 출력되는 소수는 오름차순으로 정렬한다.

 

1자리씩 점점 숫자를 늘려가며 소수인 경우만 가지를 뻗는 백트래킹 문제이다.

1자리는 2, 3, 5, 7만 가능하기 때문에 간단하게 작성한다.

dfs(2, 1);
dfs(3, 1);
dfs(5, 1);
dfs(7, 1);

 

dfs()의 매개변수는 현재 숫자를 뜻하는 number와 숫자의 자리수를 뜻하는 depth로 이루어져 있다. depth가 N과 같아질 때, 모든 조건을 만족한 소수이므로 number를 출력한다.

public static void dfs(int number, int depth) {
    if (depth == N) {
        if (isPrime(number)) {
            System.out.println(number);
        }
        return;
    }

	...
}

 

이때 isPrime()은 정수가 소수인지 판별하는 메서드이다. 소수라면 true, 아니라면 false를 출력하는 boolean형 메서드를 선언한다.

public static boolean isPrime(int n) {
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}

 

이제 현재 number에서 숫자를 이어나가며 소수인지 판별해야 한다.

오른쪽에 이어나간 숫자는 일단 짝수가 되면 안되므로 홀수만 판별한다. 현재 number에 10을 곱하고 0이 된 1의 자리에 숫자를 연결하면 새롭게 만든 다음 자리 숫자가 완성된다. 이를 isPrime()으로 소수인지 판별하고, 만약 소수라면 새로 만든 숫자와 자리수 + 1을 한 전달인자를 가지는 dfs()를 호출한다.

for (int i = 1; i < 10; i += 2) {
    if (isPrime(number * 10 + i)) {
        dfs(number * 10 + i, depth + 1);
    }
}

 

 

전체 코드 (Java)

import java.util.Scanner;

public class Main {
	static int N;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();

		dfs(2, 1);
		dfs(3, 1);
		dfs(5, 1);
		dfs(7, 1);
	}

	public static void dfs(int number, int depth) {
		if (depth == N) {
			if (isPrime(number)) {
				System.out.println(number);
			}
			return;
		}

		for (int i = 1; i < 10; i += 2) {
			if (isPrime(number * 10 + i)) {
				dfs(number * 10 + i, depth + 1);
			}
		}
	}

	public static boolean isPrime(int n) {
		for (int i = 2; i <= n / 2; i++) {
			if (n % i == 0)
				return false;
		}

		return true;
	}
}

 

 

후기

소수라는 조건에 너무 얽매여 더 쉬운 풀이법이 있는 것을 알아채지 못했다. 자리수를 증가시킬 때도 괜히 문자열로 형변환을 하고 다시 Integer로 만드려는 멍청한 생각을 했다. 쉽게 쉽게 푸는 것이 제일 어려운 것 같다.