[Python] 백준 9613 GCD합

코드 작성

import math
n = int(input())
for _ in range(n):
    k = list(map(int, input().split()))
    sum = 0
    for i in range(1,len(k)):
        for j in range(i+1, len(k)):
            sum += math.gcd(k[i],k[j])
    print(sum)

코드  풀이

#1. GCD(Greatest Common Divisor)

최대 공약수는 math 모듈을 불러와서 파이선에 내장되어 있는 함수를 사용한다.

cf) LCM(Least Common Multiple): 최소공배수

 

#2. i와 i+1비교

k의 리스트중 0번째를 제외한 1번째부터 비교할텐데

1번째와 2,3,4번째

2번째와 3,4,번째

3번째와 4번째

이렇게 반복하기 위해 for문을 2번 사용한다.

    for i in range(1,len(k)):
        for j in range(i+1, len(k)):
            sum += math.gcd(k[i],k[j])

#3.

gcd의 값을 sum에 계속 추가하면서 그 합을 구한다.