[파이썬(Python)] 백준 9613번 GCD 합

 

 

백준 9613번: GCD 합

문제 바로 가기

---

📌 문제

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

입력

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

출력

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

 

 

 

📝 문제 접근 방법

문제 분석

모든 테스트 케이스에서 주어진 숫자들의 쌍에 대해 GCD를 계산하고 그 합을 출력해야 합니다.

 

아이디어

1. 가능한 모든 쌍 만들기

• $n$개의 숫자에서 가능한 모든 두 숫자의 쌍을 만듭니다.
• 예를 들어 $[10, 20, 30]$이라면
  • 생성되는 쌍은 $(10, 20), (10, 30), (20, 30)$입니다.
  • 총 쌍의 개수는 조합의 개수로 계산되며 $\binom{n}{2} = \frac{n(n-1)}{2}$개 입니다.
• itertools.combinations를 사용하여 조합을 생성합니다.

 

2. 각 쌍의 GCD 계산

• 생성된 쌍 $(a, b)$에 대해 math.gcd(a,b)를 사용하여 두 숫자의 GCD를 계산합니다.
• 각 쌍의 GCD 값을 누적하여 가능한 모든 쌍의 GCD 합을 구합니다.

 

 

 

👩‍💻 나의 답안

🌱 깃허브

from math import gcd
from itertools import combinations

for _ in range(int(input())):
    n, *arr = map(int, input().split())

    result = 0
    for a, b in combinations(arr, 2):
        result += gcd(a, b)
    print(result)