[백준/BOJ] 1735번: 분수 합

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

1735번: 분수 합

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

해설

최소공배수(LCM, Least Common Multiple), 최대공약수(GCD, Greatest Common Divisor)

이 두 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다.

 

우선 최대공약수를 구하는 알고리즘을 알아보자.

유클리드 호재법을 이용하면 간편하게 구할 수 있다.

fun GCD(x: Int, y: Int): Int {
    return if(x % y == 0) y
    else GCD(y, x % y)
}

 

최대공배수를 보자.

두 수 M과 N이 있으면 M * N = 최대공약수 * 최소공배수가 성립된다.

따라서 유클리드 호재법을 이용하여 구해놓은 최대공약수를 M * N의 값에 나눠주면 된다.

 

이제 분자와 분모를 구했다.

이를 기약분수 형태로 나타내야 한다.

따라서 분자와 분모의 최대공약수를 구하여 각각 나눠주면 기약분수 형태가 된다.

소스 코드

fun main() = with(System.`in`.bufferedReader()){
    val (a, b) = readLine().split(" ").map { it.toInt() }
    val (c, d) = readLine().split(" ").map { it.toInt() }
    val gcd = GCD(b, d)
    val lcm = b * d / gcd
    val numerator = lcm / b * a + lcm / d * c
    val gcd2 = GCD(lcm, numerator)
    println("${numerator / gcd2} ${lcm / gcd2}")
}

fun GCD(x: Int, y: Int): Int {
    return if(x % y == 0) y
    else GCD(y, x % y)
}