백준 1644번 소수의 연속합 - 스위프트(Swift) 풀이

---

 

1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다.
2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다.

 

1. 에라토스테네스의 체를 사용하여 4,000,000 이하인 소수 목록을 구한다.

 일단 소수들을 구해야 한다. N=4,000,000이므로 4,000,000 이하인 소수 목록을 다 구한다. 에라토스테네스의 체를 사용하면 O(NloglogN)에 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. 그리고 나서 소수들만 추려 배열을 만든다.

 

2. 소수 목록에서 투 포인터를 사용하여 연속합이 N이 되는 경우를 모두 구한다.

 연속하는 모든 구간을 탐색하는 것은 불가능하다. 소수 개수(M)가 약 280,000개 이므로 O(M^2)의 시간 복잡도로는 통과할 수 없다. 결국 "연속"해야만 하므로 투포인터를 사용하여 O(M)에 연속합이 N이 되는 모든 경우를 카운트할 수 있도록 한다.

 소수 목록을 이미 다 구했으므로, 이제 2003번과 같은 문제가 된다. 연속합이 N보다 작을 때는 구간을 늘리고, N보다 클 때는 구간을 줄이면서 합이 N이 될 때마다 카운트를 해준다.

2003번: 수들의 합 2

반응형

---

import Foundation

var isPrime = Array(repeating: true, count: 4_000_001)
var primeNumbers = [Int]()

func getPrimeNumbers() {
    isPrime[1] = false
    
    for i in 2...4_000_000 {
        guard isPrime[i] else { continue }
        
        var x = i * 2
        while x <= 4_000_000 {
            isPrime[x] = false
            x += i
        }
    }
    
    for i in 2...4_000_000 {
        if isPrime[i] { primeNumbers.append(i) }
    }
}

func countNumberOfCases(_ n: Int) -> Int {
    var s = 0, e = 0, sum = 2, count = 0
    
    while true {
        if sum > n {
            sum -= primeNumbers[s]
            s += 1
        } else if sum == n {
            count += 1
            sum -= primeNumbers[s]
            s += 1
        } else {
            guard e < primeNumbers.count-1 else { break }
            e += 1
            sum += primeNumbers[e]
        }
    }
    
    return count
}

func solution() {
    let N = Int(readLine()!)!
    
    getPrimeNumbers()
    print(countNumberOfCases(N))
}

solution()