[Kotlin, S4] 백준 2090번 조화평균

출처: unsplash.com

 

조화평균(2090번)

Silver 4

#수학 #구현 #정수론 #유클리드 호제법

 

문제 내용

 

 

문제 접근

입력받는 수들을 모두 역수로 바꾼 값들의 합을 분수 형태로 변환 후 그 값의 역수를 출력하는 문제이다.

1, 2, 4가 들어왔으면 1 + 1/2 + 1/4 = 7/4를 역수로 출력해서 정답이 4/7이 되는 방식이다.

 

입력값들의 역수를 더하려면 통분이 필요한데, 통분은 입력값들의 최소공배수를 이용해 통분을 진행하면 된다.

주의해야 하는 점은 출력을 가장 적은 수의 문자를 사용하는 답을 출력하라고 돼 있는데, 이를 쉽게 풀면 약분해서 출력하라는 뜻이기 때문에 약분까지 진행해서 출력해야 한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    val list = bf.readLine().split(" ").map { it.toLong() }
    var numerator = 0L       // 분자
    var denominator = 1L     // 분모

    for (i in list.indices) {
        val gcd = gcd(denominator, list[i])
        denominator = (denominator * list[i]) / gcd
    }

    for (i in list.indices) {
        numerator += denominator / list[i]
    }

    val reduction = gcd(denominator, numerator)
    println("${denominator / reduction}/${numerator / reduction}")
}

private fun gcd(a: Long, b: Long): Long {
    return if (b == 0L) a
    else gcd(b, a % b)
}

 

문제 풀이

입력값들을 반복문에서 최대공약수를 구하고, 최대공약수를 이용해 최소공배수를 구해 준다.

분모를 확정 짓고, 분모를 기반으로 통분을 진행해서 분자도 구해준다.

 

그다음 약분을 진행해 분자와 분모의 최대공약수를 구하고

분모 / 최대공약수, 분자 / 최대공약수를 출력한다.

 

 

문제 해결 과정

타입이 Int 범위를 넘어서는 경우가 있을 수 있다.

Long 타입으로 지정해 주자. 

Int 범위를 벗어나는지는 이 예제를 확인하면 알 수 있다.

input:
9
97 89 87 83 79 71 67 61 59

answer: 
84314287678878321/10126009550065045

 

위에서도 언급했다시피, 분자와 분모를 구하고 나서 약분하는 것을 잊지 말자, 약분하지 않고 제출하면 40%에서 오답 처리가 될 것이다.