-
1735. [Python]분수 합Python_알고리즘/Silver III 2023. 5. 23. 21:24
1. 문제
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 유클리드 호제법
3. 파이썬 코드
import math # 분수로 나타낼 수들을 각각 input 으로 받아온다 A,B = map(int,input().split()) C,D = map(int,input().split()) # 분모의 최소공배수를 구한다 lcm = math.lcm(B,D) # 분자에 각각 분모의 최소공배수에서 기존의 분모를 나눈 몫을 곱해준다 A = A*(lcm//B) C = C*(lcm//D) # 두 분자의 합을 구한다 total = A+C # 분자와 분모가 약분이 되는지 확인 gcd = math.gcd(total,lcm) # 분자와 분모의 최대공약수로 나눠준다. print(total//gcd,lcm//gcd)
4. 문제를 풀고난 후 생각
- 두 분수가 주어진 경우 두 분수에서 분모의 최소공배수를 구하여 그 구한값을 바탕으로 분수의 합을 구하는 방식을 사용했다.
- 두 분수의 합을 구한 후 분수가 약분이 되는지 확인하는 과정을 분자와 분모의 최대공약수로 나눠주는 방식으로 간단히 해결함.
5. 문제를 푸는데 도움이 되는 지식
- 유클리드 호제법
- 최대공약수 최소공배수(math 함수)
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1614. [Python]영식이의 손가락 (0) 2023.05.26 2012. [Python]등수 매기기 (0) 2023.05.24 1935. [Python]후위 표기식2 (0) 2023.05.23 10974. [Python]모든 순열 (0) 2023.05.21 1003. [Python]피보나치 함수 (0) 2023.05.19