[백준9613번] GCD합 / Python3

문제

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

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

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

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

예제 출력 1

70
3
35

나의 풀이

처음에 각 테스트 케이스의 입력에서 n과 n개의 숫자가 주어진다는 조건을 빼먹고 읽어 문제를 해결하지 못했었다... 문제를 이제 집중해서 잘 읽어야겠다는 깨달음을 얻었다..ㅋㅋㅋ

이 문제는 각 테스트케이스에서 주어지는 숫자들을 모두 짝지어서 나오는 최대공약수들을 더해주면 됐다. gcd를 구하는 함수를 만들어두고 모든 경우를 탐색했다. i를 0부터 주어진 배열의 길이 - 1만큼 반복시키고 j를 i부터 주어진 배열의 길이만큼 반복을 하면서 가능한 모든 짝을 지어주었다. 그리고 gcd를 구하기 위해서는 매개변수로 주어지는 a가 b보다 작아야 한다. 그래서 처음에 숫자들을 입력받을때 정렬을 해서 탐색을 해주었다.

코드

# 9613번 GCD합
import sys

# gcd
def gcd(a,b):
    while True:
        if a == 0:
            return b

        tmp = a
        a = b % a
        b = tmp

# main
T = int(input())

for _ in range(T):
    nums = [int(x) for x in sys.stdin.readline().split()]
    n = nums.pop(0)     # 맨 앞의 n을 pop
    nums.sort()     # a가 b보다 큰 경우를 막음

    # 가능한 최대공약수들
    sumOfGcd = 0
    for i in range(len(nums)-1):
        for j in range(i+1,len(nums)):
            sumOfGcd += gcd(nums[i],nums[j])

    print(sumOfGcd)