[백준][코틀린] 1644 소수의 연속합

문제 내용

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력	예제 출력
20	0
3	1
41	3
53	2

문제 풀이

본 문제는 비교적 간단한 문제이다! 두가지의 유형이 섞였을뿐!!

일단, 해당 숫자 밑으로 소수를 구해준다. 이 알고리즘이 바로 fun sosu! 에라테스테네스의 체를 이용하여 소수의 목록을 뽑아주었다. 이소수의 목록은 정렬이 되어있으므로 바로 사용해서 투포인터로 문제를 풀어주면 된다! (소수의 목록은 두번 작업하지 않기 위해 누적합으로 바로 구해주었음!)

투포인터를 통해 그 구간의 합이 n과 같다면 결과값을 증가시켜주고, start와 end의 포인터를 모두 증가 시켜준다.

n보다 구간의 값이 크다면 start의 값을 증가시켜 구간의 값을 줄여주고, 그렇지 않다면 end의 값을 증가시켜 구간의 값을 늘려준다. 이렇게 탐색이 끝이 나면 결과 값을 출력해주면 끝이다!

이해 되지 않는 부분은 댓글 달아주세요!

</>̆̈ 코드

fun main() {
    val n = System.`in`.bufferedReader().readLine().toInt()
    val array = sosu(n); val arraySize = array.size
    var start = 0; var end = 1; var result = 0

    while (end in start until arraySize) {
        (array[end] - array[start]).run {
            when {
                this == n -> { result++; start ++; end++ }
                this > n -> start++
                else -> end++
            }
        }
    }
    print(result)
}

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

    val list = mutableListOf(0)
    for (i in 2 .. n) if (isSosu[i]) list.add(i + list.last())

    return list.toIntArray()
}

링크

1644번: 소수의 연속합