[백준/파이썬/수학] 9613번 GCD 합 코딩테스트 연습풀이 실버3

문제 출처: https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

 

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

 

예제 입력 1

3
4 10 20 30 40
3 7 5 12
3 125 15 25

 

예제 출력 1

70
3
35

 

정답

import math
num = int(input())

for i in range(num):
    arr = list(map(int, input().split()))
    sum = 0
    for j in range(arr[0]-1):
        for x in range(j+1, arr[0]):
            sum += math.gcd(arr[j+1],arr[x+1])
    print(sum)

코드 해설에 들어가기전에 gcd는 최대공약수입니다!

 

1. 테스트 케이스의 개수를 num에 입력

2. arr에 테스트 케이스를 입력

3. 이중 for문으로 각각 수의 최대공약수를 sum에 덧셈

4. sum출력

 

위의 4단계로 걸쳐서 정답을 찾았습니다

제 코드에서 유의할 점은 마지막 gcd부분에서 j+1, x+1을 제대로 세팅해야 답을 찾을 수 있습니다!