[백준/BOJ] 1644번: 소수의 연속합

문제

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

1644번: 소수의 연속합

해설

하나의 정수를 입력받고 이를 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

즉, 입력받은 정수까지의 소수 목록을 구하는 것이 첫번째 과정이 된다.

이때 에라토스테네스의 채를 이용하여 소수 목록을 구할 수 있다.

private val primeList = mutableListOf(0)

private fun eratosthenes(n: Int) {
    val arr = BooleanArray(n + 1) { true }
    for(i in 2 .. sqrt(n.toDouble()).toInt()) {
        if(arr[i]) {
            var j = 2
            while(i * j <= n) {
                arr[i * j] = false
                j++
            }
        }
    }

    for(i in 2 .. n) {
        if(arr[i]) primeList.add(i + primeList.last())
    }
}

나는 우선 소수 목록을 구한 후, 누적합을 구해가며 리스트에 넣어주었다. 누적합으로 넣어주었기 때문에 후에 합을 계산할 때 따로 소수들의 합을 구해주지 않아도 된다.

 

이제 투포인터를 사용하여 합이 n이 되는 경우의 수를 찾으면 된다.

private fun countSum(n: Int): Int {
    var start = 0
    var end = 1
    var cnt = 0

    while(end < primeList.size) {
        val temp = primeList[end] - primeList[start]
        if(temp == n) {
            cnt++
            start++
            end++
        }
        else if(temp > n) start++
        else end++
    }
    return cnt
}

예시와 함께 코드를 확인해보자.

41이라는 정수를 만들어야 할 때, 리스트에는 0, 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160, 197, 238이 들어있게 된다.

처음 start와 end는 각각 0과 1로 2 - 0이 된다.

41보다 값이 작으므로 더 큰 값을 확인하기 위해 end를 한칸 증가시켜준다.

반대로 41보다 값이 크다면 start를 증가시켜 값을 작게 만들어주면 된다.

이를 반복하다보면 start = 0, end = 6 즉, 41 - 0이 되게 된다.

우리가 찾고자 하는 정수가 나왔으므로 경우의 수를 증가시켜주고, start와 end 또한 한칸 증가시켜준다.

반복을 마치고 나면 41 - 0, 58 - 17, 160 - 129로 총 3개의 경우의 수가 있다는 것을 확인할 수 있다.

코드

import kotlin.math.sqrt

private val primeList = mutableListOf(0)

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    eratosthenes(n)
    primeList.forEach { print("$it ") }
    println(countSum(n))
}

private fun eratosthenes(n: Int) {
    val arr = BooleanArray(n + 1) { true }
    for(i in 2 .. sqrt(n.toDouble()).toInt()) {
        if(arr[i]) {
            var j = 2
            while(i * j <= n) {
                arr[i * j] = false
                j++
            }
        }
    }

    for(i in 2 .. n) {
        if(arr[i]) primeList.add(i + primeList.last())
    }
}

private fun countSum(n: Int): Int {
    var start = 0
    var end = 1
    var cnt = 0

    while(end < primeList.size) {
        val temp = primeList[end] - primeList[start]
        if(temp == n) {
            cnt++
            start++
            end++
        }
        else if(temp > n) start++
        else end++
    }
    return cnt
}