BOJ 9613 GCD 합 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합 구하기.

GCD: 최대공약수(Greatest Common Divisor, GCD)

• 입력

첫째 줄에 테.케의 개수(1≤t≤100)

각 테.케는 한 줄로 이뤄짐.

첫번째 수는 수의 개수 n(1≤n≤100), 이후 n개의 수가 주어짐.

입력으로 주어지는 수는 백만을 넘지 않음.

• 출력

각 테.케마다 가능한 모든 쌍의 최대공약수의 합 출력

두 번째 단계 (문제 핵심 파악)

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수

→ 두수의 최대공약수를 구하는 유클리드 호제법 이용.

<유클리드 호제법>

임의의 두 자연수 a, b가 주어지고 둘 중 큰 값이 a라고 가정하자.

a를 b로 나눈 나머지를 n로 한다면(a%b = n)

n이 0일때, b가 최대공약수임

만약, n이 0이 아니라면 a에 b값을 다시넣고 b에 n를 대입하고 위 과정에서 나누기부터 반복한다.

코드 작성

import sys

input = sys.stdin.readline

n = int(input())

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

for _ in range(n):
    tc = list(map(int, input().split()))
    ans = 0
    for i in range(1, tc[0]):  # 수의 개수
        for j in range(i + 1, tc[0] + 1):  # 두 수를 짝지어 준다.
            ans += gcd(tc[i], tc[j])

    print(ans)

느낀점

유클리드호제법으로 최대공약수를 구한다.