[Kotlin] 백준 2485 : 가로수

문제 링크

2485번: 가로수

---

문제 해설

각 가로수의 거리 간격이 동일해지도록 새로운 가로수를 심어야한다. 단순히 생각하면 각 가로수 사이의 거리를 구해서 거리의 최소값 간격으로 심으면 될 것 같지만 예제 2번의 경우가 반례가 된다.

 

이 경우에는 각 가로수 사이의 거리가 4, 6, 6이 되어 최소 거리가 4가 된다. 이렇게 되면 2부터 4의 간격으로 나무를 심게 되면 [2, 6, 10, 12, 14, 18]이 되기 때문에 각 가로수 사이의 거리가 일치하지 않는다.

 

이 문제는 각 가로수 사이의 거리들의 최대 공약수를 구해서 해결할 수 있다. 이 경우, 각 가로수 사이의 거리는 최대 공약수의 배수가 되는데, 중간에 비어있는 최대 공약수의 배수를 더해주면 되는 것이다.

 

최대 공약수를 구했다면 각 가로수 사이의 거리를 최대 공약수로 나눠서 새로 심어야 할 가로수의 개수를 구할 수 있다. 이 때 거리의 끝부분에는 이미 가로수가 있기 때문에 1을 빼줘야 한다.

 

최대 공약수는 유클리드 호제법(코드의 gcd() 함수)으로 구할 수 있다.

Code

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val colonnade = IntArray(n) { readLine().toInt() }
    val distance = IntArray(n - 1) { colonnade[it + 1] - colonnade[it] }
    val gcd = distance.reduce { acc, i -> gcd(acc, i) }
    var result = 0
    for (d in distance) result += d / gcd - 1
    println(result)
}

private fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)