4037 : 분수 더하기
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 3
•통과: 3
•만든사람: suakii
문제 설명
$N$개의 분수를 모두 더한 결과를 기약분수로 출력하라.
기약분수란 분자와 분모의 최대공약수(GCD)가 1인 분수이다.
분모가 1이더라도 분자와 분모를 함께 출력한다.
[제약 조건]
• $1 \le N \le 20$
• $0 \le (\text{분자}) \le 1000$
• $1 \le (\text{분모}) \le 1000$
• 입력되는 모든 값은 정수
기약분수란 분자와 분모의 최대공약수(GCD)가 1인 분수이다.
분모가 1이더라도 분자와 분모를 함께 출력한다.
[제약 조건]
• $1 \le N \le 20$
• $0 \le (\text{분자}) \le 1000$
• $1 \le (\text{분모}) \le 1000$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 분수의 수 $N$이 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 분수의 분자와 분모가 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 분수의 분자와 분모가 공백으로 구분되어 주어집니다.
출력 설명
$N$개의 분수를 합산한 기약분수의 분자와 분모를 공백으로 구분하여 한 줄에 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1 2
1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5 6도움
분수의 덧셈: $\frac{a}{b} + \frac{c}{d} = \frac{a \times d + c \times b}{b \times d}$
합산 후 분자와 분모의 최대공약수(GCD)로 나누면 기약분수를 구할 수 있다.
GCD는 유클리드 호제법으로 계산: gcd(a, b) = gcd(b, a%b), gcd(a, 0) = a
합산 후 분자와 분모의 최대공약수(GCD)로 나누면 기약분수를 구할 수 있다.
GCD는 유클리드 호제법으로 계산: gcd(a, b) = gcd(b, a%b), gcd(a, 0) = a