알고리즘 문제(Swift) - 백준 - 9613 (GCD의 합)

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

 

 

 

각 테스트케이스마다 가능한 모든 쌍의 GCD의 합을 출력해야 한다면

GCD는 유클리드 알고리즘을 사용

각 케이스마다 자신을 제외한 모든 케이스와의 GCD를 구해야 함 → 이중 for문 사용

• i번째 배열의 값을 기준으로 이후 인덱스 값과의 GCD를 더함
• i는 테스트케이스의 수를 나타내는 0번 인덱스를 제외한, 1번 인덱스부터 전체 테스트케이스 - 1까지 (마지막 값은 비교할 수 없기 때문)
• j는 i+1 값부터 마지막까지로 할당하여 순차적으로 비교함

 

// 유클리드 호제법 - 최대 공약수 구하기
func gcd(_ a: Int, b: Int) -> Int {
    return a % b == 0 ? b : gcd(b, b: a % b)
}

let t = Int(readLine()!)!

for _ in 0..<t {
    let testCase = readLine()!.split(separator: " ").map{Int($0)!}
    let n = testCase[0] // 테스트케이스의 개수
    
    var answer = 0 // GCD의 합
    for i in 1...n-1 { // testCase[0]은 테스트 케이스의 개수를 나타내므로 1부터 시작
        for j in i+1...n {  // 각 테스트케이스 별로 모든 케이스와 비교해야 하므로 순차적으로 비교
            answer += gcd(testCase[i], b: testCase[j]) // 최대 공약수의 합
        }
    }
    print(answer)
}