백준 Swift [1735] 분수 합

난이도

실버 III

 

문제

https://www.acmicpc.net/problem/1735

1735번: 분수 합

 

내 답안

var firstInput = readLine()!.split(separator: " ").map { Int($0)! }
var secondInput = readLine()!.split(separator: " ").map { Int($0)! }

var result = [firstInput[0] * secondInput[1] + secondInput[0] * firstInput[1], firstInput[1] * secondInput[1]]

func gcd(bigOne: Int, smallOne: Int) -> Int {
    if smallOne == 0 {
        return bigOne
    }

    return gcd(bigOne: smallOne, smallOne: bigOne % smallOne)
}

print(result[0] / gcd(bigOne: result[0], smallOne: result[1]), result[1] / gcd(bigOne: result[0], smallOne: result[1]))

• 이전에 최소 공배수를 구하는 방법, 최대 공약수를 구하는 방법을 생각하며 구상했을 때에는 코드가 복잡하고 시간이 많이 소요될 것 같았다.
• 두 분수의 합을 구하는 방식은 두 분모의 최소공배수를 구하고, 각 분자에 곱하는 방법도 있고, 아예 분모끼리 곱하고 나누는 방식이 있다고 생각했다.
• 처음에 전자로 코드를 구현했을 때에는 위에 언급한 것처럼 코드가 복잡하고 틀린 결과가 나왔는데, 기약분수가 아니어서 그랬지 않았나 싶다.
• 후자로 코드를 구현하고 하니, 분모끼리 곱하고 분자를 만드는 것은 간단하나 그것을 어떻게 나눌지가 고민이었다. 분자와 분모의 최대공약수를 구하면 되지만, 이전의 그 코드를 사용하기엔 복잡해보였다.
• 검색포털에 최대공약수 공식을 검색해보았고 다음의 키워드를 얻게 되었다.

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

• gcd라는 메서드 안에서, 큰 수를 작은 수로 나눴을 때 나머지가 0이 될 때까지 반복하는 방식으로 최대공약수를 쉽게 구할 수 있다고 한다.
• 그러면 작은 수(smallOne)가 0이면 큰 수(bigOne)를 반환하고, 아니라면 해당 과정을 반복하면 될 것이다.

// 위키피디아 예시

    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

• 각 언어별 예제 코드가 있었는데, 자바의 코드가 적용하기 적합한 것 같아 반영하였다.

 public static int gcd(int p, int q)
 {
    if (q == 0) return p;
    return gcd(q, p%q);
 }