[프로그래머스] Lv.0 /분수의 덧셈 (파이썬/Python)

1. 문제 설명

2. 풀이 과정

해당 문제는 두 분수의 분자와 분모로 정의된 수를 사용하여 두 분수를 더한 값을 기약 분수로 나타내는 문제이다.

먼저 두 분수의 합의 값을 구할 줄 알아야 하며, 최대공약수를 구할 줄 알아야 한다.

두 분수의 합을 구하는 방법은 다음 공식을 수식화하면 된다.

최대공약수를 구하는 방법은 '유클리드 호제법을 이용하면 된다.

출처 : 나무위키

코드를 풀어서 설명하면, 두 분수의 합을 구하게 되면 분자는 분모보다 무조건 크기 때문에 유클리드 호제법을 사용하기 위한 기본 조건을 만족한다. 그리고 분모와 분자의 나머지가 0이 될때까지 위 공식을 적용하면 되는데, 그 이유는 최대공약수만 구하기 위해 만든 수의 법칙을 이용하는 것뿐이기 때문이다. 나머지가 존재하면 분자에 이전 분수식의 분모를 분모에는 분이전 분수식의 분자, 분모의 나머지를 놓으며 나머지가 0이 될때까지 반복한다. 

위 과정을 진행하기 위해 gcd(최대공약수)를  if문을 사용하여 따로 정의한다.

마지막으로 처음에 계산한 분수의 합의 분자,분모에 gcd를 나누어 기약 분수를 출력한다.

3. 코드