백준 9613번 Python / Math

문제 링크

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

9613번: GCD 합

 

풀이

import math
t = int(input())
answer=0

for _ in range(t):
    data = input().split()
    del data[0]
    for i in range(len(data)-1):
        cnt = len(data)
        for j in range(cnt):
            if i < j:
                answer += math.gcd(int(data[i]), int(data[j]))
    print(answer)
    answer=0

주어진 수에서 나올 수 있는 모든 최대공약수를 합하는 문제입니다.

우선 입력 받은 값(t) 만큼 문제풀이를 진행합니다.

값들을 받을 때, 첫 번째 값은 필요가 없으므로 del로 data 리스트에서 제거합니다.

그리고 for문을 두 번 반복해서 리스트 인덱스를 순회하며 math.gcd(숫자1, 숫자2)를 진행해줍니다.

단, i < j의 조건을 걸어 같은 인덱스나 수행했던 계산을 반복하지 않도록 처리해줍니다.

예를 들어 첫 줄 예제의 경우 -> gcd(0번째, 1번째), gcd(0번째, 2번째), gcd(0번째, 3번째), gcd(1번째, 2번째), gcd(1번째, 3번째) ... 이런식으로 진행하도록 처리