[백준 9613] GCD 합

1. 문제

www.acmicpc.net/problem/9613

9613번: GCD 합

2. 접근 방법

라이브러리를 쓰지 않고 시도해봐따

 

GCD(최대공약수)는 math를 쓰지 않고 유클리드 호제법을 사용하려고 했는데

기억이 나지 않아서 서치했따 !

 

brownbears.tistory.com/454

이 분이 가장 쉽게? 설명했다고 생각합니다요

 

여튼 유클리드 호제법은

x, y의 최대공약수를 구할 때

1. x % y == 0 --> gcd(x, y) = y

2. x % y != 0 --> gcd(x, y) = gcd(x, x%y)

3. x%y==0이 될 때까지 2를 반복

3. 코드

python

def GCD(lst):
    a, b = lst
    while b:
        a, b = b, a % b
    return a

def comb(cnt, N, start):
    global answer, sum_answer
    if cnt == N:
        sum_answer += GCD(answer)
        return
    else:
        for i in range(start, len(lst)):
            answer.append(lst[i])
            comb(cnt+1, N, i+1)
            answer.pop()

N = int(input())
for _ in range(N):
    lst = list(map(int, input().split()))
    lst.pop(0)
    answer = []
    sum_answer = 0
    comb(0, 2, 0)
    print(sum_answer)

4. 마치며

오랜만에 수학문제였습니다요