Kotlin] 백준 2485번 문제풀이

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

2485번: 가로수

 

 

이 문제는 최대공약수를 알아야한다.

 

왜 최대공약수를 알아야하냐고..?

자, 우리는 가능한 큰 간격으로 나무를 세워야 한다.

제시된 예시를 보자.

4
1
3
7
13

 

해당 예시를 보면,

1 3 7 13.. 사이의 간격은 2 4 6이다.

제일 이상적인 방식은 무엇인가? 2개 간격으로 나무를 심는 것이다. 1개 간격으로 나무를 심으면 나무를 너무 심어버리게 되고, 2를 넘으면 1~3 사이의 간격을 만족하지 못한다. 즉, 최대공약수로 나무를 심는 것이 제일 바람직하다.

 

최대공약수를 구하기 위해서는 유클리드 호제법이 가장 빠르므로 유클리드 호제법을 사용한다.

유클리드 호제법이 무엇인지는 링크 ㅇ.<

https://itstudy-mary.tistory.com/574

Kotlin 예시 작성] 유클리드 호제법(Euclidean Algorithm)

 

간격은 다수인데 최대공약수를 어떻게 구하냐 ㅇㅁ''ㅇ 할수도 있는데, 다수 배열의 최대공약수를 구하는 방법은.. 놀랍게도

[a, b, c] 의 최대공약수는 [(a, b), c]의 최대공약수와 일치한다.

 

예를 들어 36, 126, 648의 최대공약수를 구한다.

먼저 한꺼번에 구해보자.

약수 배열 = [2] / 남은 수: 18, 63, 324
약수 배열 = [2, 3] / 남은 수 : 6, 21, 108
약수 배열 = [2, 3, 3] / 남은 수 : 2, 7, 36

 

로 18이 나온다.

 

이제 36과 126의 최대공약수를 구하고, 그 최대공약수로 648에 대입해보자.

약수 배열 = [2] / 남은 수 : 18, 63
약수 배열 = [2, 3] / 남은 수 : 6, 21
약수 배열 = [2, 3, 3] / 남은 수 : 2, 7
최대공약수 : 2*3*3 = 18

 

일단 18이 나온걸 확인하고, 이 18을 648과 대응해보면..

약수 배열 = [2] / 남은 수 : 9, 324
약수 배열 = [2, 3] / 남은 수 : 3, 108
약수 배열 = [2, 3, 3] / 남은 수 : 1, 36
최대공약수 : 2*3*3 = 18

 

으로 동일하게 18로 나오는 것을 확인할 수 있다.

이 방식을 이용하여 배열의 앞 수로 최대 공약수를 구하고 -> 이 최대 공약수와 다음 수와의 최대공약수를 구하고 -> 다시 이 공약수로 다음 수와의 최대 공약수를 구하고... 의 형태로 최종적인 최대공약수를 구한다.

 

또한 이 문제는 '심어지는 좌표' 보다는 결국 '심어지는 나무의 갯수' 만 중요하다. 따라서 굳이 좌표의 갯수를 저장할 필요도 없고, 해당 간격이 몇 번 등장했는지~ 만 알면 된다. 따라서 해시에 간격을 key로 두고, 등장한 횟수를 value로 저장하면 된다.

 

이론은 완벽하다. 이제 코드를 보자. 좀 더 정확한 내용은 주석을 보면 알 수 있다.

fun main(args: Array<String>) {
    question2485()
}

fun question2485() {
    val count = readln().toInt()
    val list = hashMapOf<Int, Int>()

// 간격을 키로, getOrDefault를 통해 횟수를 저장.
// previous를 전역으로 설정해 좌표와 이전 좌표 사이의 간격을 구한다.
    var previous = 0
    for(i in 1 .. count) {
        val location = readln().toInt()
        if(previous != 0) {
            val key = location - previous
            list[key] = list.getOrDefault(key, 0) + 1
        }
        previous = location
    }

// prevDivider에 이전 최대공약수 값을 저장해놓고 해시를 돌며 각 키값과 비교하여 최대공약수를 구한다.
    var prevDivider = 0
    list.forEach {
        prevDivider = if (prevDivider == 0) {
            it.key
        } else {
            euclideanAlgorithm(prevDivider, it.key)
        }
    }

// 최대공약수에 맞게 심어진 나무는 굳이 새로 심을 필요 없으므로 간격과 최대공약수를 나눴을 때 몫이 1로 나오는 경우 나무를 심을 필요 없다 판단함.
    var treeCount = 0
    list.forEach {
        treeCount += (it.key / prevDivider - 1) * it.value
    }

    println(treeCount)

}

// 유클리드 호제법
fun euclideanAlgorithm(a : Int, b: Int) : Int {
    var cloneA = a
    var cloneB = b

    val result : Int
    while (true) {
        val remain = cloneA % cloneB
        if(remain == 0) {
            result = cloneB
            break
        } else {
            cloneA = cloneB
            cloneB = remain
        }
    }

    return result

}