백준 9613 GCD 합 Python 유클리드 호제법 실버4

알아야 했던 것

1. 유클리드 호제법

# 반복문
def find_GCD(b,a):
	while b != 0:
    	a,b = b , a%b
    return a\
# 재귀문
def find_GCD(a,b):
    r = a%b
    if r == 0:
        return b
    else:
        return find_GCD(b,r)

2. 두 항을 어떻게 비교해 나갈 지

실수한점 : 전체의 경우의 수를 구해놓고, 그걸 활용하려 하는 과정에서 어려움이 있어 해결하지 못함

2개의 인덱스를 가지고 처리하는것이였기 때문에

=> 선택 정렬 알고리즘을 수정해 기준 인덱스와 선택인덱스를 비교해 나가는 방식으로 풀이하면 됐었음

 

정답코드

t = int(input())

def find_GCD(a,b):
    r = a%b
    if r == 0:
        return b
    else:
        return find_GCD(b,r)

for _ in range(t):
    arr = list(map(int,input().split()))
    n = arr[0]
    num_arr = arr[1:]
    sum_v = 0
    for i in range(n-1): # n-1 과 n 번째 인덱스를 비교해야되기 때문
        for j in range(i+1,n):
            sum_v += find_GCD(num_arr[i],num_arr[j])
    print(sum_v)