[백준 2023번] [Kotlin] 신기한 소수

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

2023번: 신기한 소수

 

난이도 : 골드 5
태그 : 수학, 정수론, 백트래킹, 소수 판정

 

 

설명

백트래킹 + 소수판정 문제입니다.

백트래킹으로 수열을 구한 뒤, 수열을 숫자로 바꿔 해당 숫자가 소수인지 판단하였습니다.

 

 

 

소스코드

 

시간초과

var n = -1
lateinit var nums: Array<Int>
val sb = StringBuilder()

fun main() {
    n = readln().toInt()
    nums = Array(n) { -1 }

    backTracking(0)

    print(sb)
}

fun backTracking(depth: Int) {

    if (depth == n) {
        if (nums[n - 1] % 2 != 0 && isPrime(depth - 1)) sb.append(nums.joinToString("")).append("\n")
        return
    }

    val start = if (depth == 0) 2 else 0

    for (i in start until 10) {
        nums[depth] = i
        if (isPrime(depth)) backTracking(depth + 1)
    }
}

fun isPrime(idx: Int): Boolean {

    var sum = 0
    for (i in 0..idx) {
        sum = sum * 10 + nums[i]

        for (j in 3 until sum) {
            if (sum % j == 0) return false
        }
    }

    return true
}

 

하지만 시간초과가 났습니다.

소수의 자리수는 최대 8개로, 10 ^ 8 까지입니다. 네... 모든 수열을 다 체크하니까 시간초과 날만했네요.

 

 

안되면 미리 쳐내기

lateinit var nums: Array<Int>
var n = -1
val sb = StringBuilder()

fun main() {
    n = readln().toInt()
    nums = Array(n) { -1 }

    backTracking(0)

    print(sb)
}

fun backTracking(depth: Int) {

    if (depth == n) {
        if (isPrime(depth - 1)) sb.append(nums.joinToString("")).append("\n")
        return
    }

    val start = if (depth == 0) 2 else 0

    for (i in start until 10) {
        nums[depth] = i
        if (isPrime(depth)) backTracking(depth + 1)
    }
}

fun isPrime(idx: Int): Boolean {

    var sum = 0
    for (i in 0..idx) {
        sum = sum * 10 + nums[i]

        for (j in 2 until sum) {
            if (sum % j == 0) return false
        }
    }

    return true
}

 

1000 ~ 1999는 1이 소수가 아니기 때문에 1으로 시작하는 숫자는 찾을 필요가 없습니다.

2의 배수인 4, 6, 8로 시작하는 숫자 역시 찾을 필요가 없죠.

 

즉, 백트래킹을 할 때마다 어차피 안되는 수들은 미리 쳐내는 방법으로 시간초과를 해결할 수 있었습니다.

 

 

 

후기

백트래킹은 언제해도 재밌습니다. 짜릿합니다. 너무 좋아.