몽상실현개발주의

[BOJ] 9613 / GCD 합 / Python 파이썬 본문

Algorithm PS/BOJ

[BOJ] 9613 / GCD 합 / Python 파이썬

migrationArc 2021. 5. 30. 15:57

[BOJ] 9613 / GCD 합 / Python 파이썬

[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)
Comments