백준 문제 풀이 - GCD 합 9613번

📜 문제 이해하기

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

💡 문제 재정의

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

✏️ 계획 수립

가능한 모든 쌍의 값들을 유클리드 호제법을 이용해서 문제를 풀면 된다.

💻 계획 수행

import sys


# 유클리드 호제법
def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    N = int(sys.stdin.readline())
    for _ in range(N):
        num_list = list(map(int, sys.stdin.readline().rstrip().split()))
        case = num_list.pop(0)
        if case > 1:
            result = 0
            for i in range(case):
                for j in range(i+1, case):
                    result += get_gcd(num_list[i], num_list[j])
            print(result)
        else:
            print(num_list.pop())

🤔 회고

유클리드 호제법을 알아야 시간안에 풀 수 있는 문제이다.