[6개월 안에 백준 플래티넘 달성하기] 22. 소수의 연속합

소수의 연속합

1644번: 소수의 연속합

 

문제

 

풀이

문제를 처음 봤을 때는 DP풀이를 생각해 봤습니다. 하지만 규칙을 찾지 못하여 다른 풀이를 찾게 되었습니다.

 

N의 수가 4,000,000으로 매우 크기 때문에 해당 범위 안에 있는 소수의 개수가 적을 경우 좀 더 다양한 풀이를 생각할 수 있다고 생각하여 에라토스테네스의 체를 이용하여 소수를 구해주었습니다.

 

N이 4,000,000일 때 소수의 개수는 대략 20만 개로 여전히 n제곱의 알고리즘은 사용할 수 없었습니다.

그렇게 소수를 나열한 상태로 방법을 찾아봤습니다.

 

결국에는 연속된 수만 허용되기 때문에 투 포인터로 가능할 거 같았습니다.

0의 인덱스부터 합을 구하면서 N보다 합이 작을 경우에는 오른쪽으로 이동하며 값을 더해주고 N보다 클 경우에는 왼쪽의 값을 빼주는 식으로 진행하여 해결해 주었습니다.

 

import kotlin.math.sqrt

fun main() {

    val num = readln().toInt()

    val arr = BooleanArray(num+1) {true}
    arr[0] = false
    arr[1] = false
    // 에라토스테네스의 체
    fun findPrime(){

        for (i in 2 .. sqrt(num.toFloat()).toInt()) {
            if (arr[i]) {
                for (j in i*i..num step i) {
                    arr[j] = false
                }
            }
        }
    }
    findPrime()

    // 소수만 따로 리스트에 담아줌
    val list = mutableListOf<Int>()
    for (i in 0..num) {
        if (arr[i]) list.add(i)
    }

    // 투 포인터
    var result = 0
    var left = 0
    var right  = 0
    var sum = 0
    while (left <= right) {

        if (sum < num) {
            if (right == list.size)
                break
            sum += list[right]
            right++
        } else if (sum >= num) {
            if (sum == num) result++
            sum -= list[left]
            left++
        }
    }
    print(result)
}

 

 

시간초과가 발생할 경우
1. 에라토스테네스의 체를 제대로 구현했는지 확인
2. 투 포인터에서 최적화할 부분이 있는지 확인
3. 연결 리스트를 썼는지 확인  (본인 얘기 LinkedList 쓰는 실수함..)