1. 문제 설명

네 개의 소수

2. 문제 분석

네 개의 소수의 합을 통해 특정 수 N을 구한다. N이 짝수라면 4를 미리 빼주고 (2+2), 홀수라면 5를 미리 빼주자(2+3). 남은 수를 두 소수의 합으로 만들기 위해 에라토스테네스의 체와 조합을 사용했다.

3. 나의 풀이

import Foundation

var N = Int(String(readLine()!))!
var boxes = Array(repeating: true, count: N+1)
boxes[0] = false
boxes[1] = false
for idx in 2..<boxes.count {
    if boxes[idx] {
        if idx * 2 < boxes.count {
            for idx2 in stride(from: idx * 2, to: boxes.count, by: idx) {
                boxes[idx2] = false
            }
        }
    }
}

let filteredBoxes = boxes.enumerated().filter{$0.element}.map{$0.offset}

let prefix: [Int]
var answer = [Int]()
if N % 2 == 0 {
    N -= 4
    prefix = [2, 2]
} else {
    N -= 5
    prefix = [2, 3]
}

func depthFirstSearch(_ count: Int, _ numbers: [Int], _ sum: Int) {
    if !answer.isEmpty {
        return
    }
    
    if count == 2 {
        if sum == N && answer.isEmpty {
            answer = numbers
        }
        return
    }
    
    for idx in 0..<filteredBoxes.count {
        let number = filteredBoxes[idx]
        if number + sum <= N {
            depthFirstSearch(count + 1, numbers + [number], sum + number)
        }
    }
}

depthFirstSearch(0, [], 0)
if answer.isEmpty {
    print(-1)
} else {
    answer = prefix + answer
    for number in answer {
        print(number, terminator: " ")
    }
}