[백준/BOJ] 9613번: GCD 합

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

9613번: GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

해설

유클리드 알고리즘(유클리드 호제법)을 알면 어려울 게 없다고 생각한다.유클리드 알고리즘은 2개의 자연수가 있을 때 서로 상대방 수를 나누어 원하는 값을 얻는 알고리즘이다.

fun GCD(a: Int, b: Int): Int {
    return if(a % b == 0) b
    else GCD(b, a % b)
}

main 함수에서 이중 for문을 통해 두 수를 뽑고 최대공약수를 더하여 출력하면 된다.

 

주의할 점으로는 입력으로 주어지는 수가 최대 1000000이기 때문에 n이 100이고 모두 1000000일 경우 답이 int 범위를 초과하게 된다. 

따라서 gcdSum의 변수형을 Long으로 해줘야 한다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val st = StringTokenizer(readLine())
        val n = st.nextToken().toInt()

        val arr = IntArray(n)
        for(i in 0 until n) arr[i] = st.nextToken().toInt()

        var gcdSum: Long = 0
        for(i in 0 until n-1) {
            for(j in i + 1 until n) {
                gcdSum += GCD(arr[i], arr[j])
            }
        }
        println(gcdSum)
        gcdSum = 0
    }
}

fun GCD(a: Int, b: Int) : Int {
    return if(a % b == 0) b
    else GCD(b, a%b)
}