백준 Swift [17103] 골드바흐 파티션

난이도

실버 II

 

문제

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

내 답안

import Foundation

var testBed = [Bool](repeating: true, count: 1000000)
testBed[0] = false
testBed[1] = false

for i in 2..<Int(sqrt(Double(testBed.count))) + 1 {
    var j = 2

    while i * j <= testBed.count && testBed.indices.contains(i * j) {
        testBed[i * j] = false
        j += 1
    }
}

for _ in 1...Int(readLine()!)! {
    let input = Int(readLine()!)!

    var count = 0

    for i in 1...input / 2 {
        if testBed[i] && testBed[input - i] {
            count += 1
        }
    }

    print(count)
}

• 너무 고통스러운 문제
• 이 문제도 골드바흐의 추측 혹은 파티션으로 검색하면 흔히 쓰는 공식이 있어 스위프트 코드로 써볼 수 있지 않을까 했는데 없더라.
• 그래서 기본적으로 생각했던 방식은 이전에 소수인지 아닌지 판별하던 메서드를 Bool값을 반환하는 식으로 변경해서, 주어진 값을 2로 나눈 범위 안에서 돌면서 i와 input - i 값이 둘 다 true라면 count를 증가시켜 그것을 출력하는 방식을 생각했다.
• 하지만 전부 시간 초과가 났고..수많은 코드 변경으로 느낀 것은 test 메서드를 두 번 돌리는 것이 시간이 오래 걸린다는 것?
• 매번 메서드 돌리는 것이 시간이 오래 걸린다면 사전에 범위의 수를 소수인지 아닌지 판별해놓고 주어진 값에 대해 파티션의 수만 얻으면 되겠다 생각을 하게 되었는데, 범위의 수가 1,000,000까지이기에 이 과정 또한 시간이 너무 오래 걸릴 것 같았다.
• 하지만 기존 소수 판별 메서드의 루트 N까지만 확인하는 것을 이용하면 줄어들 것이고 그 방법을 적용한 결과 해결할 수 있었다.
  
  
• 1) testBed에 범위(1,000,000)만큼 true를 반복해서 대입(소수인지 아닌지의 Bool)
  2) 0과 1은 소수가 아니기에 testBed[0], testBed[1]은 false
  3) 2부터 루트 N + 1미만까지 for문을 돌면서 j를 사용하여(j가 1이면 모든 수가 false가 되기에 2부터 시작) testBed의 값을 바꿔주기로 함
  4) i * j가 testBed의 count(1,000,000)보다 같거나 작고, i * j가 testBed의 index 범위 안에 있다면 testBed[i * j]는 false로 바꾸고 j의 값을 증가시킨다.
  indices를 조건에 추가한 이유는, 가령 i * j가 count 조건에는 부합하는 1,000,000이라면 testBed의 인덱스로 들어가면 out of range 오류가 나기 때문(0부터 시작이라 1,000,000 - 1이 마지막 인덱스)
  곱한 값을 false로 처리하는 이유는, 소수는 1과 자기자신만이 약수인 수이기에 1 * 자기자신 만 가능하기 때문
  5) 이렇게 완성된 testBed를 사용하여 for문을 1부터 input을 2로 나눈 수까지 돌면서(두 소수의 순서만 다른 것은 같은 파티션이므로) testBed의 i와 input - i가 true라면(둘 다 소수라면) count를 증가하는 식으로 문제를 해결할 수 있었음
• 결과적으로 기존에 메서드를 통해 소수인지 확인했던 것을 사전에 정리된 배열을 통해서 확인만 하는 식으로 시간을 줄일 수 있었다.

고통의 흔적