https://www.acmicpc.net/problem/20003
시간 1초, 메모리 512MB
input :
- N (1 ≤ N ≤ 50)
- 분자 A, 분모 B (1 ≤ A, B ≤ 40)
output :
- 코인 단위의 분자, 분모를 공백으로 구분하여 출력
이 문제도 생각이 짧았다....
우선 입력의 분모를 눈여겨 보다가 최소 공배수로 나오는 것을 확인하고 이를 구했다.
이 때까지만 해도 분자는 1로 고정인 줄 알았다.
그러나, 분모의 단위가 바꼈기에 입력받은 분자들의 값도 바뀐다. 그리고 이를 이용해 우리는 최대 공약수를 찾을 수 있고
분자와, 분모의 최대 공약수로 새로 만들 코인 단위를 더 줄일 수 있다.
이를 간과 한 것이 시간을 잡아먹는 큰 이유 였다.
import sys
from math import gcd
n = int(sys.stdin.readline())
down = []
up = []
for i in range(n):
a, b = map(int, sys.stdin.readline().split())
up.append(a)
down.append(b)
ans_down = down[0]
for i in range(1, n):
temp = gcd(ans_down, down[i])
ans_down = ans_down * down[i] // temp
for i in range(n):
up[i] *= ans_down // down[i]
ans_up = up[0]
for i in range(1, n):
ans_up = gcd(ans_up, up[i])
temp = gcd(ans_up, ans_down)
print(ans_up // temp, ans_down // temp)
