[파이썬] 백준 - 9613: GCD 합

---

문제

9613번: GCD 합

---

풀이

for이 세 개 이상 겹쳐 나온다면 합리적 의심을 해 보아야 한다.

시간 효율이 미친듯이 떨어지기 때문이다.

역시 나만 모르는 인싸들의 도구가 있었으니....

import itertools

lists = [1, 2, 3]
permut = list(itertools.permutations(lists, 2))
comb = list(itertools.combinations(lists, 2))

print('순열: {} \n조합: {}'.format(permut, comb))

permutations는 순열, combinations는 조합을 쉽게 출력해낸다(끝에 s 주의!).

순열은 (1, 2)와 (2, 1)를 다른 경우의 수로 취급한다.

조합은 (1, 2)와 (2, 1)를 하나로 취급한다.

 

문제로 돌아가자.

 

1.  최대공약수를 구하는 함수를 정의.

2.  입력받은 테스트 케이스 수로 for문 만듬.

3.  순서대로 테스트 케이스들을 입력 받는데, 사실 위의 방법을 이용하면 첫번째로 받는 테스트 케이스 수는 필요가 없다. 또한, 최대공약수 구하는 함수는 x로 y를 나누어야 하기 때문에 입력받는 수들을 내림차순 정렬해야한다. 정리: 내림차순 정렬 후, 마지막 요소를 제거한다.

4.  combinations를 써서 result에 최대공약수들을 더하고 프린트한 후엔 result를 0으로 만든다.

5.  3부터 반복

from itertools import combinations

def gcd(x, y):	# 최대공약수 계산 함수
    while y:
        x, y = y, (x % y)
    return x

n = int(input())
lists = []
result = 0
for _ in range(n):
    lists = list(map(int, input().split()))	# 조합 만들 숫자들 받기
    lists = lists[::-1]	# 내림차순 정렬
    del lists[len(lists) - 1]	# 마지막 요소 필요 없으니 제거
    ncr = combinations(lists, 2)	# 조합 생성
    
    for i in ncr:
        result += gcd(i[0], i[1])	# 조합을 통해 최대공약수들 result에 더하기
    print(result)	# 프린트 해 두고
    result = 0	# 초기화