관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 2023 신기한 소수 -백트랙킹- 자바 코틀린 본문

알고리즘/DFS, BFS, 시뮬, 백트래킹

[알고리즘] 백준 2023 신기한 소수 -백트랙킹- 자바 코틀린

막무가내막내 2021. 2. 21. 13:43
728x90

 

 

 

 

그동안 시간관계상 알고리즘 풀이를 못하였는데 약 두달만에 풀어봤네요. 오랜만의 풀이라 안그래도 없던 알고리즘 실력도 다 떨어졌는데 주요 알고리즘과 스탠다드한 문제 풀이로 감도 되찾고 실력을 쌓으려고합니다.. ㅎㅎ 시간 여유도 생겼으니 열심히 해야겠습니다. 

 

youngest-programming.tistory.com/382

 

[알고리즘] 스터디 계획표

현재 하고있는것들이 있어 좀 밀렸지만 최대한 계획 맞춰서 공부

youngest-programming.tistory.com

예전 공부 계획표 참고하면서 분류당 한문제씩 풀어볼까 생각중입니다.

 

 


www.acmicpc.net/problem/2023

 

2023번: 신기한 소수

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

www.acmicpc.net

오늘은 백준 2023 신기한 소수 문제를 풀어봤습니다.

N자리수의 자연수들 중 1의자리부터 N자리까지 모두 소수인 자연수를 판별하는 문제로

소수랑 백트랙킹이 엮인 스탠다드한 문제였습니다.

 

처음 다음과 같이 에라토스테네스의 체로 최대 자리수의 소수판별 배열을 만들어서 풀이했는데 메모리 초과로 통과하지못하였습니다.

import java.util.Scanner;

class Main {
    private static int N;
    private static boolean[] prime;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        int max = (int) Math.pow(10f, N); // N=2 -> 100
        prime = new boolean[max];
        makePrime(max);
        dfs("", 0);
        System.out.println(sb.toString());
    }

    private static void dfs(String num, int depth) {
        if (depth == N) {
                sb.append(num).append("\n");
            return;
        }
        for (int i = 1; i <= 9; i++) {
            int currentNum = Integer.parseInt(num + i);
            if (!prime[currentNum]) {
                dfs(currentNum + "", depth + 1);
            }
        }

    }

    private static void makePrime(int n) {
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }


}

 

 

그래서 소수판별방식을 그떄그떄 수를 매개변수로 받아서 판별하게 변경으로써 통과할 수 있었습니다.

풀이는 다음과 같습니다.

[Java]

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs("", 0);
        System.out.println(sb.toString());
    }

    private static void dfs(String num, int depth) {
        if (depth == N) {
            sb.append(num).append("\n");
            return;
        }
        for (int i = 1; i <= 9; i++) {
            int currentNum = Integer.parseInt(num + i);
            if (isPrime(currentNum)) {
                dfs(currentNum + "", depth + 1);
            }
        }

    }

    private static boolean isPrime(int n) {
        // 0, 1
        if (n < 2) return false;
        // 2
        if (n == 2) return true;

        for (int i = 2; i < n; i++) {
            // 소수 X
            if (n % i == 0) return false;
        }
        return true;
    }


}

 

[Kotlin]

import java.util.*


private var N = 0
private val sb = StringBuilder()
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    dfs("", 0)
    println(sb.toString())
}

private fun dfs(num: String, depth: Int) {
    if (depth == N) {
        sb.append(num).append("\n")
        return
    }
    for (i in 1..9) {
        val currentNum = (num + i).toInt()
        if (isPrime(currentNum)) {
            dfs(currentNum.toString() + "", depth + 1)
        }
    }
}

private fun isPrime(n: Int): Boolean { 
    if (n < 2) return false // 0, 1
    // 2
    if (n == 2) return true
    for (i in 2 until n) { // 소수 X
        if (n % i == 0) return false
    }
    return true
}

 

 

뎃글과 공감은 큰 힘이 됩니다. 감사합니다.!!

728x90
Comments