[백준 9613 파이썬/python] GCD 합

GCD 합 다국어

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

2)

3)

GCD 합 다국어

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	31447	12642	10352	41.042%

문제

양의 정수 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

풀이

1)

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


t = int(input())

for _ in range(t):
    lst = []
    cmd = list(map(int, input().split()))
    for i in range(1, cmd[0]):
        for j in range(i + 1, cmd[0] + 1):
            lst.append(gcd(cmd[i], cmd[j]))
    print(sum(lst))

2)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
t = int(input())
for _ in range(t):
    a = list(map(int, input().split()))
    n = a[0]
    a = a[1:]
    ans = 0
    for i in range(0, n-1):
        for j in range(i+1, n):
            ans += gcd(a[i], a[j])
    print(ans)

3)

import sys
from math import gcd

def main():
    t = int(input())
    for _ in range(t):
        nums = list(map(int, sys.stdin.readline().split()))
        n = nums.pop(0)
        gcd_sum = 0
        for i in range(n):
            for j in range(i+1, n):
                gcd_sum += gcd(nums[i], nums[j])
        print(gcd_sum)

if __name__ == "__main__":
    main()

세 답안의 풀이과정은 비슷하고 변수의 사용이나 코드의 간결성에 대한 차이만 존재한다. 따라서 마지막 코드에 대한 풀이과정만 진행하겠다.

• 풀이과정
  1. import sys와 from math import gcd: 이 부분은 코드에서 사용할 라이브러리들을 가져옵니다. sys는 입력을 처리하기 위해 사용되고, math의 gcd 함수는 최대공약수를 구하기 위해 사용됩니다.
  2. main() 함수를 정의합니다. 이 함수는 문제를 해결하는 주요 코드입니다.
  3. t = int(input()): 테스트 케이스의 개수를 입력받습니다.
  4. for _ in range(t):: 각 테스트 케이스에 대해 반복합니다.
  5. nums = list(map(int, sys.stdin.readline().split())): 각 테스트 케이스에 대한 숫자들을 입력받아 리스트에 저장합니다.
  6. n = nums.pop(0): 입력받은 리스트의 첫 번째 숫자는 n에 저장하고, 리스트에서 제거합니다. 이 n은 숫자의 개수를 나타냅니다.
  7. gcd_sum = 0: 가능한 모든 쌍의 최대공약수(GCD)의 합을 저장할 변수를 초기화합니다.
  8. 이중 for문을 사용하여 가능한 모든 쌍에 대해 최대공약수를 구하고, gcd_sum에 누적합니다.

     for i in range(n):
         for j in range(i+1, n):
             gcd_sum += gcd(nums[i], nums[j])

  9. print(gcd_sum): 각 테스트 케이스마다 계산된 GCD의 합을 출력합니다.

  마지막으로, if __name__ == "__main__": 라인에서 main() 함수를 호출하여 문제를 해결하는 코드를 실행합니다. 이렇게 구성된 코드를 사용하면 문제에서 요구하는 가능한 모든 쌍의 최대공약수의 합을 구할 수 있습니다.

Uploaded by N2T