백준 2023 신기한 소수 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

문제

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

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 정수론
• 백트래킹
• 소수 판정

풀이

소수 + 백트래킹 문제다.

출력을 보고 1도 소수로 쳤었나? 뭐지? 생각했었는데 문제 조건을 다시 읽어보니

앞에서부터 1,2,3,4~N을 확인해야 한다. 무슨 말이냐면

2939가 있으면

2, 29, 293, 2939를 확인해야 하기 때문에 뒤에는 첫 번째 자리만 1이 오지 않으면 괜찮다는 의미이다.

문제 잘 읽자.

 

풀이는 간단하다.

백트래킹으로 한 자리수씩 1~9 숫자를 채워나가며 해당 수가 소수가 아니라면 탐색을 멈추고, 소수라면 계속 탐색하면 된다.

fun checkPrime(num: Int): Boolean {
    for (i in 2..Math.sqrt(num.toDouble()).toInt()) {
        if (num % i == 0) return false
    }
    return true
}

소수인지 확인하는 것은 이렇게 간단하게 할 수 있다.

확인하려는 수가 81이라면 9까지만 해당 수로 나누어 떨어지는지 확인하면 된다.

이렇게 소수인지 확인해가며 N번 째 숫자가 완성된다면 출력하면 된다.

애초에 숫자를 넣어줄 때, 1~9 순서대로 넣으면 따로 정렬은 하지 않아도 된다.

코드

val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
var n = 0
fun checkPrime(num: Int): Boolean {
    for (i in 2..Math.sqrt(num.toDouble()).toInt()) {
        if (num % i == 0) return false
    }
    return true
}

fun backTracking(len: Int, result: Int) {

    //소수 검사
    if (len > 0 && !checkPrime(result)) return

    if (len == n) {
        bw.write("$result\n")
        return
    }
    for (i in 1..9) {
        if(len==0 && i == 1) continue
        backTracking(len + 1, result * 10 + i)
    }
}

fun main() {
    n = getInt()
    backTracking(0, 0)
    br.close()
    bw.close()
}