[Python] 백준 9613 - GCD 합 문제 풀이

Overview

BOJ 9613번 GCD 합 Python 문제 풀이
분류: Math (수학)

---

문제 페이지

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

---

풀이 코드 1 - 유클리드 호제법

from sys import stdin


def get_gcd(a: int, b: int) -> int:
    if b == 0:
        return a

    return get_gcd(b, a % b)


def main():
    t = int(stdin.readline())
    for _ in range(t):
        nums = list(map(int, stdin.readline().split()))

        res = 0
        for i in range(1, len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] < nums[j]:
                    res += get_gcd(nums[i], nums[j])
                else:
                    res += get_gcd(nums[j], nums[i])

        print(res)


if __name__ == "__main__":
    main()

가능한 모든 수 조합에서 최대공약수를 구하고, res에 더해가며 답을 구한다. 최대공약수를 구할 때에는 유클리드 호제법을 이용하였다.

---

풀이 코드 2 - itertools, math

from sys import stdin
from itertools import combinations
from math import gcd


def main():
    t = int(stdin.readline())
    for _ in range(t):
        nums = list(map(int, stdin.readline().split()))

        res = 0
        combs = combinations(nums[1:], 2)
        for a, b in combs:
            res += gcd(a, b)

        print(res)


if __name__ == "__main__":
    main()

두 개의 수를 고를 때, itertools 라이브러리의 combinations 함수를 이용하였다. 그리고 최대공약수를 구하는 함수를 구현하지 않고 math 라이브러리의 gcd 함수를 이용하였다.