[Python] 백준 9613번 - GCD 합

 

9613번: GCD 합

문제

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

 

입력

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

 

출력

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

 

import math

t = int(input())
for _ in range(t):
    n, *arr = map(int, input().split())
    tot = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            tot += math.gcd(arr[i], arr[j])
    
    print(tot)

gcd는 최대공약수입니다. 학부생 시절 노교수님의 이산수학 시간에 배웠었는데, 다 까먹어서 공부하고 풀었습니다;; 각설하고 최대공약수란 두 숫자가 서로소인 수가 될때까지 나눈 몫을 곱하여 나온 수를 의미합니다. 10과 20의 최대공약수는 10이 되겠네요.

 

이 문제는 리스트에 저장된 모든 수의 쌍으로 최대공약수를 찾고 그 최대공약수를 모두 더한 값을 찾는 것입니다. gcd를 따로 구현하지 않기 위해 math 모듈을 사용했습니다. gcd 앞에 위치시키기 위해 처음부터 마지막 인덱스 - 1과 두 번째부터 마지막 인덱스까지 쌍을 만들고 총합을 구했습니다. 예를 들어 arr에 저장된 값이 [10, 20, 30, 40]이라면 arr[i]는 10부터 30까지만, arr[j]는 20부터 40까지만 표현합니다.

 

피드백은 언제나 환영합니다.