백준 [1644] - kotlin

[문제]

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

1644번: 소수의 연속합

[풀이]

투 포인터를 이용하면 쉽게 풀 수 있는 문제이다.

 

문제를 푸는 방법은 아래와 같다.

 

1. 조건  N의 범위가 (1 ≤ N ≤ 4,000,000) 이므로, (1 ≤ N ≤ 4,000,000) 사이의 소수를 미리 모두 구한다.

2. 연속된 소수의 합이므로, 연속된 소수의 합을 미리 구하여 배열에 저장을 해둔다.

3. 투 포인터를 이용하여, 풀어준다.

 

1번 과정은 에라토스테네스의 체를 이용하여 해결한다.

prime = MutableList(MAX){true}
prime[1] = false
prime[0] = false
for(i in 2 until sqrt(MAX.toFloat()).toInt()){
   for(j in (i*2) until MAX step(i)) {
      prime[j] = false
   }
}

 

2번 과정은 빈 배열을 만들어 두고, 합을 갱신하여 배열에 추가하면 된다.

prime_sum = mutableListOf(0)
var psum = 0
for(i in 2 until prime.size) {
    if(prime[i]) {
       psum += i
       prime_sum.add(psum)
    }
}

3번 과정이 가장 중요하다.

투 포인터를 이용하여 푸는데, 합이 저장이 되어있는 prim_sum배열에서 두 개의 포인터를 이동시키면서 정답을 구한다.

두 개의 포인터를 각각 left, right라고 가정하고, 아래의 과정을 반복해준다.

 

1. prime_sum[right] - prime_sum[left] 가 N보다 큰 경우 

    -> 구간 합이 N보다 크므로, left를 한칸 오른쪽으로 이동시켜 작게 만들어주어야 한다.

 

2. prime_sum[right] - prime_sum[left] 가 N보다 작은 경우 

    -> 구간 합이 N보다 작으므로, right를 한칸 오른쪽으로 이동시켜 크게 만들어주어야 한다.

 

3. 이외의 경우

   -> 이외의 경우에는 구간 합이 N과 같으므로, 값을 찾은 것이다. 하지만, 본 문제는 모든 경우의 수를 알아야 하므로, while문의 종료 조건에 만족하기 위해 right를 한칸 오른쪽으로 이동시켜주어야 한다.

 

종료조건은 

left가 right보다 커지거나, right가 prime_sum 배열의 크기보다 커지게 되면 종료한다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.sqrt

lateinit var prime : MutableList<Boolean>
lateinit var prime_sum : MutableList<Int>
val MAX = 4000001
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val N = br.readLine().toInt()

    if(N == 1) {
        bw.write("0")
    }
    else {
        prime = MutableList(MAX){true}
        prime[1] = false
        prime[0] = false
        for(i in 2 until sqrt(MAX.toFloat()).toInt()){
            for(j in (i*2) until MAX step(i)) {
                prime[j] = false
            }
        }
        prime_sum = mutableListOf(0)
        var psum = 0
        for(i in 2 until prime.size) {
            if(prime[i]) {
                psum += i
                prime_sum.add(psum)
            }

        }

        var ans = 0
        var left = 0
        var right = 0
        while (left <= right && right < prime_sum.size){
            if(prime_sum[right] - prime_sum[left] > N){
                left++
            }
            else if(prime_sum[right] - prime_sum[left] < N) {
                right++
            }
            else{
                ans++
                right++
            }
        }
        bw.write(ans.toString())
    }

    bw.flush()
    bw.close()
}