[python] 백준 9613번

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

문제

---

소스코드

import sys
from itertools import combinations


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


for _ in range(int(sys.stdin.readline())):
    n = list(map(int, sys.stdin.readline().split()))

    com = list(combinations(n[1:], 2))

    g = 0
    for i in range(len(com)):
        g += gcd(com[i][0], com[i][1])

    print(g)

---

풀이

• GCD의 합이란 예를 들어 (10, 20, 30, 40)의 입력을 받으면 gcd(10, 20) + gcd(10, 30) + gcd(10, 40) + ... 을 의미한다.
• math 모듈의 gcd를 사용하지 않고 유클리드 호제법에 따라 gcd 함수를 만들어 사용한다.
• 조합(combination)은 itertools를 편의상 사용했지만 이중 for문을 사용한 것과 시간복잡도 측에서 필요에 따라 결과가 다를 수 있다.