[python] 백준 9613번 GCD 합

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

9613번: GCD 합

 

 

 

---

 

 

💻 코드

 

import sys
import math

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    sum_gcd = 0
    num = list(map(int, input().split()))

    n = num[0]
    for i in range(1, n):
        for j in range(2, n + 1):
            if i < j:
                sum_gcd += math.gcd(num[i], num[j])

    print(sum_gcd)

 

 

 

 

📝 풀이

 

최대 공약수를 구하는 문제인데 입력된 리스트에서 가능한 모든 쌍의 최대공약수의 합을 구해야 했다.

입력 수를 리스트로 만들고 이 수를 쌍을 지어야 하는데 먼저 가능한 쌍을 나열해보면서 규칙을 찾아보았다.

 

 

🔅 10 20 30 40을 예로 들면,

 

10 20 30 40

[0] [1] [2] [3]

 

 

가능한 쌍은

 

(10, 20) (10, 30) (10, 40) (20, 30) (20, 40) (30, 40) 

 

으로 6가지가 나온다.

 

 

 

리스트로 접근해야 하므로 인덱스로 나타내 보면

 

(0, 1) (0, 2) (0, 3)

         (1, 2) (1, 3)

                  (2, 3)

 

이와 같이 나타나므로 이중 반복문을 사용해야 함을 알 수 있다. (시간 초과가 날 줄 알고 또 걱정했는데 괜찮았다.)

 

 (i, j)로 두면

i = 0     j = 1~3

i = 1     j = 2~3

i = 2     j = 3    

 

그런데 코드에서는 인덱스[0]이 n에 해당하기 때문에 +1씩이라고 생각하면 된다.

 

이중 for문을 이용해서 i는 0부터 2까지, j는 1부터 3까지 하고

조건문을 이용하여 i < j일 때만 최대공약수를 구하도록 해주면 결과값이 맞게 나온다.

 

 

 

 

계산 과정을 상세히 보면서 하면 틀린 부분을 쉽게 찾을 수 있다.

 

 

* 최대 공약수는 math 라이브러리에 있는 gcd 함수를 사용하여 구했다.