문제 링크

🤔 풀이 방법

문제에서 캐치해야 할 것은 아래와 같다.

1. 주어진 숫자 중 3개의 수를 더한다.
2. 서로 다른 3개를 골라 더했을 때, 소수가 되느냐?

재귀 함수를 이용해서 서로 다른 3개의 수를 선택하면 1번 조건이 충족된다.
하지만, 2번의 조건을 충족시키려면 어떻게 해야 할까? 답은, 에라토스테네스 체 이다.

알고리즘의 순서는 다음과 같다.

1. 에라토스테네스의 체를 이용해서 2부터 1000까지 반복문을 수행하면서 소수인 값을 저장한다. 
2. 재귀 함수를 이용하여 서로 다른 3개의 수를 구하고 합한 값이 1번에서 저장된 소수 리스트에 포함되는지 판단하여 포함될 경우, 개수를 센다.

👉 소스 코드

class Solution {
    lateinit var check: BooleanArray
    private val primeChecked = BooleanArray(3001)
    private val prime = mutableListOf<Int>()
    private var count = 0

    fun solution(nums: IntArray): Int {
        check = BooleanArray(nums.size)

        for (i in 2 until primeChecked.size) {
            if (!primeChecked[i]) {
                primeChecked[i] = true
                prime.add(i)
                for (j in i..primeChecked.size step (i)) {
                    primeChecked[j] = true
                }
            }
        }

        recursive(0,0,0,nums)
        return count
    }

    private fun recursive(depth: Int, sum: Int, next: Int, nums: IntArray) {
        if (depth == 3) {
            if (prime.contains(sum))
                count++
            return
        }

        for (i in next until nums.size) {
            recursive(
                depth = depth + 1,
                sum = nums[i] + sum,
                next = i + 1,
                nums = nums
            )
        }
    }
}