BaekJoon 9613 - GCD 합 (Python)

이번에는 아이디어 적인 부분에서 나름 창의적으로 한 것 같아서 풀이를 공유하기 설렌다!

 

내가 생각한 아이디어는 다음과 같다.

 

1. 두 수를 분수꼴로 나타낸다. (이 때, 분수는 기약분수가 된다.)

 

2. 나눠진 수를 분자로 나누면 GCD 등장!

 

이 아이디어면 소수를 따로 판별할 필요 없이 가능하다.

 

예시를 두 개 들어서 설명해 보겠다.

 

숫자 30과 45가 있다고 가정해 보면, 1번에 의해 30/45인 2/3이 나타나게 된다.

 

이후 2번에 의해 30/2 = 15가 나타나게 되는데, 이는 GCD이다.

 

하나 더, 숫자 3과 7이 있다고 가정해 보면, 1번에 의해 3/7이 나타나게 된다.

 

이후 2번에 의해 3/3 = 1이 나타나게 되는데, 이 역시 GCD이다.

 

 

이 행위가 가능한 이유를 보면, "기약 분수"로 표현한다는 것 자체가 GCD로 나눠진 값이다.

 

즉, GCD로 나눠진 값을 원래 값으로 나누면 GCD가 나타나게 되는 것!

 

이 아이디어를 구현하기 위해서 combinations와 Fraction library를 import 하였다.

 

from itertools import combinations    # 수학에서의 조합을 사용할 수 있게 해주는 library
from fractions import Fraction    # 분수식으로 표현할 수 있게 해주는 library
import sys
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

n = int(input())    # 테스트 케이스의 개수
for _ in range(n):
    answer = 0    # 정답을 저장하는 변수
    num, *numbers = map(int, input().strip().split(' '))    # 개수와 숫자들을 모두 입력받는 방법

    for (num1, num2) in list(combinations(numbers, 2)):    # numbers에서 2개씩 뽑는 조합을 진행
        f = Fraction(num1, num2)    # num1과 num2를 분수식으로 표현 (이 때, 기약분수로 표현됨)
        answer += num1 // f.numerator    # num1을 분자로 나눈다면 GCD (num2을 분모로 나눠도 동일)

    print(answer)    # 정답 출력

 

숫자를 입력받는 방법을 모른다면 Asterisk를 검색해보길 권장한다.