BOJ-1644 소수의 연속합 Swift

문제

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

내가 푼 풀이

접근방법: 투포인터, 에라토스테네스의 체

주어지는 N의 최댓값이 400만이고 시간제한은 2초이므로, 에라토스테네스의 체를 이용하여 소수를 구할 수 있다.

에라토스테네스의 체를 이용한 소수구하기 알고리즘은 많은 메모리가 필요하지만 시간복잡도가 O(NloglogN) 이므로 4000000횟수까지 연산이 된다.

 

에라토스네테스의 체

1. 2부터 구하고자 하는 범위의 최댓값까지 자연수를 나열한다.

2. 나열된 자연수중 걸러지지않은 가장 작은 자연수를 구한다.

3. 자신을 제외한 자신의 배수를 모두 거른다.

4. 더이상 반복할 수 없을때까지 반복

 

소수를 걸러내기 위해 2부터 N까지 반복한다면, 시간초과가 뜰것이다.

여기서 시간복잡도를 개선하기위해,

자연수 N은 2부터 N의 제곱근까지 모든 자연수와 나누어 떨어지지 않는다면, 이는 소수임을 이용한다.

 

N이 400만이면 N의 제곱근인 2000까지 배수를 모두 걸러내면 된다.

2에서 400만 사이의 소수를 배열에 담는다.

 

투포인터

왼쪽인덱스부터 출발하는 투포인터 알고리즘을 사용한다.

left: 0, rigt:0 으로 시작하여, left부터 right까지의 모든 원소의 합(sum)을 주어진 N과 비교한다.

N과 sum이 같다면: 경우의수 + 1, left+1, sum -= arr[left]

N보다 sum이 크다면: left -= 1 sum -= arr[left]

N보다 sum이 작다면: right += 1, sum += arr[right]

(만약 right가 마지막원소를 넘긴다면 left를 증가시켜도 sum이 증가되지않으므로 탈출)

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력받기
let N = Int(readLine()!)!
var num = 4000000
var arr = Array(repeating: true, count: num+1)
var primeNums = [Int]()
let sqrtNum = Int(sqrt(Double(num)))
arr[1] = false
// 에라토스테네스의 체를 활용하여 소수 구하기
for i in 2...sqrtNum {
    if arr[i] == true {
        var j = 2
        while i * j <= num {
            arr[i * j] = false
            j += 1
        }
    }
}
// 구했던 소수를 배열에 저장
for i in 2...num {
    if arr[i] {
        primeNums.append(i)
    }
}

var lidx = 0
var ridx = 0
var cnt = 0
var sum = primeNums[lidx]

// 투포인터 알고리즘
// 주어진 소수배열에서 왼쪽인덱스부터 오른쪽 인덱스까지의 합을 N과 비교한다.
// N이 된다면 cnt + 1 , N보다 작다면 오른쪽인덱스를 증가, N보다 크다면 왼쪽인덱스를 증가
// N이 작아서 오른쪽 인덱스를 늘려서 배열의 마지막인덱스를 초과한다면, 범위를 벗어난경우이고 왼쪽 인덱스를 올려도 합계 자체는 오르지 않기때문에 탈출
while lidx < primeNums.count && lidx <= ridx {
    if primeNums[lidx] > N { break }
    if sum == N {
        cnt += 1
        sum -= primeNums[lidx]
        lidx += 1
    } else if sum > N {
        sum -= primeNums[lidx]
        lidx += 1
    } else if sum < N {
        ridx += 1
        if ridx > primeNums.count - 1 {
            break
        }
        sum += primeNums[ridx]
    }
}

print(cnt)