[백준] GCD 합

출처:: www.acmicpc.net/problem/9613

분류:: 유클리드 

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

  1. 유클리드

#GCD 합
#https://www.acmicpc.net/problem/9613
import sys
from itertools import combinations
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
t=int(input())

for _ in range(t):
    arr=list(map(int,input().split()))
    selected=list(combinations(arr[1:],2))
    gcd = [] #gcd저장
    for a,b in selected: #가능한 쌍에서
        if a==0 or b==0:
            continue
        if a>b: #b쪽을 큰 수로 고정
            a,b=b,a
        while a!=0:
            a,b=b%a,a #나머지, 나누는 수
        gcd.append(b)
    print(sum(gcd))

 

3. 오답원인

 

4. 알게된 점

유클리드 구현

1) a,b중에 큰 수 고정시키기

2) 작은 수가 0보다 클때까지

3) (작은수 , 큰 수) = (나머지, 나누는 수) 반복 

4) 마지막 나누는 수가 최대공약수