[백준] 2023번: 신기한 소수 - Kotlin[코틀린]

문제

 

2023번: 신기한 소수

 

---

풀이

 

 입력받은 자릿수의 모든 수를 차례대로 소수 판정하는 것은 시간이 오래걸린다. 대신, 신기한 소수는 왼쪽의 한 자리 수부터 소수여야 한다는 점을 이용하여 경우의 수를 줄일 수 있다. 백트래킹을 이용해 현재 소수인 수들만 다음 자리수를 더한 소수를 찾는 탐색을 진행하면된다.

 

 먼저 신기한 소수가 되려면 첫째 자리 수가 소수인 2, 3, 5, 7 중 하나여야 한다. 그 외의 수로 시작하는 수는 다음 단계로 진행하지 않는다. 예를 들어 첫째 자리가 2인 경우에 0부터 9까지 다음 자릿수를 더해주고 소수를 찾는다. 23과 29가 소수이고 세 자리 소수를 찾는 단계로 진행할 수 있는 수가 된다.

 

 찾으려는 자릿수에 도달하면 최종적으로 소수인지 판별하고 출력해주면 된다.

 

---

 

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val sb = StringBuilder()

    fun isPrime(num: Int): Boolean {
        for(i in 2 until num) { // 약수가 있으면 소수가 아님
            if (num % i == 0) return false
        }
        return num > 1 // 1은 소수가 아님
    }

    fun checkNum(cur: Int, num: Int) {
        if(num == 0) {
            if(isPrime(cur)) sb.append("$cur\n")
            return
        }
        for(i in 0 until 10) {
            val next = cur*10 + i // 다음 자릿수를 더한 수
            if(isPrime(next)) checkNum(next, num-1)
        }
    }

    checkNum(0, num)

    bw.write(sb.toString())
    bw.flush()
    bw.close()
    br.close()
}