[백준알고리즘] 9613번: GCD 합 -Python

[백준알고리즘] 9613번: GCD 합 -Python

https://www.acmicpc.net/problem/9613

9613번: GCD 합

이번에는 최대공약수를 구하기 위해 math 모듈의 gcd를 사용했다. 처음에는 유클리드 호제법을 이용해 메서드를 만든 후 사용하도록 짰는데, 다른 분이 사용한 것을 보고 수정했다. 이런 게 있는지 처음 알았따..

 

모든 조합을 찾기 위해서 이중 for문을 돌리려다가 itertools의 combinations를 사용했다. combinations(iter, num)을 통해 iter의 원소 num개를 사용한 조합 쌍을 만들어냈다. 이 조합쌍을 list로 변환시킨 후에 각 숫자 쌍마다 gcd를 구해줬다.

 

별거 없는데 math의 gcd를 사용한 것을 찾기 위해서 작성했다.

import sys
from itertools import combinations
from math import gcd

testcase = int(sys.stdin.readline())
gcd_table = {}

for _ in range(testcase):
    nums = map(int, sys.stdin.readline().split()[1:])
    pair = list(combinations(nums, 2))
    res = 0
    for p in pair:
        if p in gcd_table.keys():
            res += gcd_table[p]
        else:
            gcd_table[p] = gcd(p[0], p[1])
            res += gcd_table[p]
    sys.stdout.write(str(res) + "\n")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다