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

해당 문제는 dfs를 이용하여 작성 할 수 있습니다.

문제에 대한 설명을 보면 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수 라고 말하고 있습니다.

즉 1의 자리를 제외하고 2,3,5,7 만 10,100,1000,...,10000000 의 자리수에 들어 갈 수 있습니다.

1의 자리에는 1,3,5,7,9가 들어 갈 수 있습니다.

 

그렇다면 시작을 2,3,5,7 부터 시작하여 그 뒤에 1,3,5,7,9을 붙이면서 N의 자리수를 가진 숫자를 만들면서 소수인지 체크 하면 해당 문제에 대한 코드를 작성 할 수 있음을 알 수 있습니다.

 

하기는 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.math.sqrt

var N = 0
var bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() {
    //val s = System.currentTimeMillis()
    val br = BufferedReader(InputStreamReader(System.`in`))

    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    dfs(2,1)
    dfs(3,1)
    dfs(5,1)
    dfs(7,1)

    bw.flush()
    bw.close()
}

fun dfs(num: Int, len:Int){
    if(len == N) {
        if(!check(num)) return
        bw.appendLine("$num")
    }
    for (i in 1..9) {
        if(check(num)){
            dfs((num*10) + i, len + 1)
        }
    }

}

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