jae_coding

(백준 알고리즘 문제풀이) 9613번 GCD합 본문

알고리즘 문제/수학(math)

(백준 알고리즘 문제풀이) 9613번 GCD합

재코딩 2022. 7. 28. 15:10
반응형

문제

문제 링크

 

문제 접근.

  • 배열 슬라이싱 사용하여 Input list 를 해결한다.
  • itertools의 combination을 사용하여 중복을 허용하지 않는 조합을 만들어 낸다.
  • math. gcd 사용하여 최대 공약수 도출한다.

코드

import sys, math
from itertools import combinations

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    input_list = list(map(int, input().split()))
    sum_gcd = 0
    for i in combinations(input_list[1:], 2):
        a, b = i
        gcd = math.gcd(a, b)
        sum_gcd += gcd
    print(sum_gcd)
반응형
Comments