본문 바로가기
Algorithm/문제풀이_백준

Swift) 백준 9020번 (골드바흐의 추측)

by Joahnee 2021. 8. 14.

요구능력 : 에라토스테네스의 체를 응용할수 있느냐

 

코드설명 : 

문제에서 10000보다 작거나 같은 모든 짝수 n이라고 했으므로, 에라토스테네스의 체를 이용해서 10000까지의 소수를 구해준다.

이후에 for문을 이용하여 테스트케이스만큼 골드바흐파티션을 구해줄것이다.

절반의수를 두 번 더하면 하나의 수가 나온다. ex) 4 = 2 + 2, 8 = 4 + 4

이 원리를 이용하면 쉽게 풀리는 문제이다.

8 = 4 + 4니까, 소수끼리 더한게 아니다.

그럼, 여기서 p1에서 1을 빼고 p2에서 1을 더해보면 결국 결과값은 8이 나온다.

(혹시나 설명해주면 에라토스테네스의 체를 만들어놨기 때문에 arr[p1]의 값은 p1이다.)

if문을 이용해서 arr[p1] + arr[p2]가 구하고자하는 값(scan)과 같으면 소수 + 소수의 조건과 차가 가장작은것이라는 조건을 둘다 만족하게 된다.

1. arr에 있는 값중 소수가 아닌값들은 모두 0이기 때문이다.(소수 + 소수의 조건)

2. 차가 0인 부분에서 부터 서서히 차를 늘려가기 때문에 적합한 수가 나오면 그게 정답이맞다.(차가 가장작은것이라는 조건)

 

후기 : 가장 작은 차를 구할 때는 가운데부터 시작해서 차를 늘려가면 된다.

let T = Int(readLine()!)!

let n = 10000
var arr: [Int] = Array(repeating: 0, count: n + 1)
for i in 2...n {
    arr[i] = i
}

for k in 2...n {
    for j in stride(from: k + k, through: n, by: k) {
        arr[j] = 0
    }
}

for _ in 1...T {
    let scan = Int(readLine()!)!
    var p1 = scan / 2
    var p2 = scan / 2
    while true{
        
        if (arr[p1] + arr[p2]) == scan {
            print("\(p1) \(p2)")
            break
        }else {
            p1 -= 1
            p2 += 1
        }
    }
}

댓글