[알고리즘/Swift] BOJ 1644 소수의 연속합 - 투 포인터 & 에라토스테네스의 체

이미지를 누르면 문제로 연결됩니다.

👀 필요한 공부

에라토스테네스의 체

• 소수를 판별하는 알고리즘. 

 

투 포인터

• 일차원 배열에서 두 개의 포인터를 지정해 계산하는 방법

 

💡 풀이 방법

위에서 언급한 두 개념을 전부 적용해서 문제를 풀면 됩니다. 먼저, 에라토스테네스의 체를 이용해 소수를 찾습니다. 찾은 소수 배열을 통해 투 포인터로 접근해서 연속된 소수의 합으로 N 이 만드는 경우의 수를 체크하면 됩니다!

 

• checkPrimes 함수 :: 에라토스테네스의 체를 이용해 소수를 판별하는 함수
• findSeries 함수 :: 투 포인터를 이용해 연속된 소수의 합으로 자연수를 나타낼 수 있는 경우의 수를 세는 함수 

 

🐥 Swift 풀이

// 소수의 연속합
func checkPrimes(n: Int, isPrimes: inout [Bool]) {
    // 2 부터 n 까지 소수인지 확인한다.
    for i in 2...n {
        if isPrimes[i] == false { continue }
        var j = i * 2 // i 의 배수를 소수목록에서 제외한다.
        while j <= n {
            isPrimes[j] = false
            j += i // i 의 배수만 확인한다
        }
    }
}

func findSeries(n: Int, primes: [Int]) -> Int {
    // 하나 이상 연속된 소수의 합으로 자연수를 나타낼 수 있는 경우의 수 세기
    // 투 포인트 :: 일차원 배열에서 두 개의 포인트를 움직이며 체크하는 것
    var start = 0, end = 0
    var sum = 0
    var count = 0
    
    while end <= primes.count {
        if sum >= n {
            // sum 이 목표값보다 크면 start 값을 제외하고, 오른쪽으로 한칸 이동
            sum -= primes[start]
            start += 1
        } else {
            // sum 이 목표값보다 작으면 end 값을 추가하고, 오른쪽으로 한칸 이동
            if end < primes.count { sum += primes[end] }
            end += 1
        }
        if sum == n {
            // 새로 계산한 sum 값이 목표와 같으면 경우의 수 카운트
            count += 1
        }
    }
    return count
}

func BOJ_1644() {
    let N = Int(readLine()!)!
    guard N > 1 else {
        print(0)
        return
    }
    
    var isPrimes = Array(repeating: true, count: N+1)//1000001)
    checkPrimes(n: N, isPrimes: &isPrimes)
    var primes: [Int] = []
    
    for i in 2 ... N {
        if isPrimes[i] == true {
            //print(i)
            primes.append(i)
        }
    }
    print(findSeries(n: N, primes: primes))
}

---

참고 블로그

투 포인터

• https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-투-포인터

에라토스테네스의 체 

• https://velog.io/@max9106/Algorithm-에라토스테네스의-체