문제
N개의 자연수가 주어질 때, 이 수들의 역수의 합의 역수를 기약분수 형태로 출력하라.
입력
첫째 줄에 N, 둘째 줄에 N개의 자연수가 주어진다.
출력
분자/분모 형태의 기약분수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 2 3 6 | 1/1 |
풀이
모든 수의 LCM을 공통 분모로 사용하여 역수의 합을 분수로 계산한 뒤 기약분수로 만든다.
- 모든 수의 LCM을 구한다 (분모 통일)
- 각 수에 대해
LCM / a_i를 계산하여 모두 합산한다 (통분된 분자의 합) - 결과 분수는
LCM / 합이다 - GCD로 약분하여 기약분수로 출력한다
핵심 아이디어: LCM을 이용해 분수 연산을 정수 연산으로 변환하고, GCD로 약분하여 정확한 기약분수를 구한다.
코드
import sys
input = sys.stdin.readline
n = int(input().rstrip())
A = list(map(int, input().rstrip().split()))
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def lcm(a, b):
return abs(a * b) // gcd(a, b)
def multi_lcm(lst):
result = lst[0]
for l in lst[1:]:
result = lcm(result, l)
return result
de = multi_lcm(A)
nu = 0
for a in A:
a = de // a
nu += a
g = gcd(de, nu)
print(f"{de // g}/{nu // g}")복잡도
- 시간: O(N * log(max A)) — LCM 계산의 GCD 반복
- 공간: O(N) — 입력 배열