Algorithm PS/BOJ
[BOJ] 9613 / GCD 합 / Python 파이썬
migrationArc
2021. 5. 30. 15:57
[BOJ] 9613 / GCD 합 / Python 파이썬
https://www.acmicpc.net/problem/9613
9613번: GCD 합
첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진
www.acmicpc.net
풀이
N 개 정수의 정수쌍 조합을 구하고, 그 쌍들의 최대 공약수 합을 구하는 문제이다.
combinations 과 gcd method 를 이용해서 구하였다.
import sys
from itertools import combinations
import math
T = int(sys.stdin.readline())
for _ in range(T):
nums = list(map(int, sys.stdin.readline().split()))
combi = list(combinations(nums[1:], 2))
res = 0
for com in combi:
res += math.gcd(com[0], com[1])
print(res)