[파이썬] 백준 9613번 「GCD의 합」

문제

백준 9613번/실버4

 

 

 

문제 해설

GCD(Greatest Common Divisor)이란 최대공약수를 의미한다. 테스트 케이스를 입력받고 테스트 케이스만큼의 각 경우의 답을 구하는 문제인데, 

각 경우는 각 수들의 모든 쌍들의 최대 공약수를 더해서 테스트 케이스마다 출력을 해줘야하는 문제이다.

 

 

 

풀이전략

보통 우리가 초중학교때 최대공약수를 구하는 방법에는 소인수 분해를 하여 구하는 것이었으나, 코딩테스트 쪽에서는 유클리드 호제법을 많이 사용한다고 한다.

원리같은 것은 잘 모르겠고, 두 줄 요약하자면

1.  a에서 b를 나눴을 때 나머지가 0이면 종료 -> 몫이 최대 공약수 , 그렇지 않다면 2번으로 이동
2.  1번에서 나온 나머지를 c라고 하였을 때, b에서 c를 나누어줌. 나머지가 0이면 종료->이때의 몫이 최대공약수, 아니면 2번 반복

 

파이썬에서는 math 모듈에서 gcd(a, b) 함수가 구현되어 있으므로 우리는 이것을 이용하면 된다.

모든 쌍을 전부 돌아야 하므로 i = 1일때 j는 2, 3, 4를 돌아야하고, i는 2일때 3, 4를 돌고, i = 3일때 j 는 4를 돌면 모든 경우의 수를 다 구할 수 있다.

 

 

코드

import sys;
import math;

n = int(sys.stdin.readline().rstrip()); #n 입력 (테스트 케이스 입력)

for _ in range(n): #테스트 케이스 반복
    lst = list(map(int, sys.stdin.readline().split())); #요소 개수, 요소들 입력
    del lst[0]; #요소 개수 삭제(파이썬에서는 필요 없음)
    
    s = 0; #GCD 의 합 저장할 변수
    for i in range(0, len(lst)-1): #맨 앞부터 맨끝-1 까지
        for j in range(i+1, len(lst)): #현재 위치 다음부터 끝까지
            s+=math.gcd(lst[i], lst[j]); #gcd를 구하고 s에 넣기
            
    print(s); #출력

 

결과

 

 

고찰

모듈 최고...!