요구능력 : 에라토스테네스의 체를 응용할수 있느냐
코드설명 :
문제에서 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
}
}
}
'Algorithm > 문제풀이_백준' 카테고리의 다른 글
Swift) 백준 3009번 (네 번째 점) (0) | 2021.08.15 |
---|---|
Swift) 백준 1085번 (직사각형에서 탈출) (0) | 2021.08.15 |
Swift) 백준 4948번 (베르트랑 공준) (0) | 2021.08.09 |
Swift) 백준 1929번 (소수구하기) (0) | 2021.08.08 |
Swift) 백준 11653번 (소인수분해) (0) | 2021.08.07 |
댓글