[파이썬] 백준 9613번: GCD합

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

9613번: GCD 합

from itertools import combinations

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def sum_gcd(lst):
    length = lst[0]
    numbers = lst[1:]
    if length == 1:
        return numbers[0]
    elif length == 2:
        return gcd(numbers[0], numbers[1])
    else:
        comb = combinations(numbers, 2)
        comb = list(comb)
        ans = 0
        for i in range(len(comb)):
            tmp_gcd = gcd(comb[i][0], comb[i][1])
            ans += tmp_gcd
        return ans

for _ in range(int(input())):
    lst = list(map(int, input().split()))
    print(sum_gcd(lst))

 

유클리드 호제법으로 푸는 방법입니다.

- 만약 받은 list의 길이가 1일 경우 그대로 반환

- 2일 경우 두 개의 숫자의 gcd 반환

- 3 이상이면 2개씩 combination을 구한 뒤 각 combination의 gcd를 구해 더하는 방식으로 풀기