[백준] [02485] [코틀린] 가로수

문제

• 플랫폼 : 백준
• 번호 : 02485
• 제목 : 가로수
• 난이도 : Silver 4
• 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다
• 문제 : 링크

---

생각

문제에서 주어진 예시를 먼저 분석합니다.

1,3,7,13 사이에 나무를 균등하게 심어야하는데 현재 주어진 나무 사이의 간격은 2,4,6입니다.

이들의 최대공약수인 2 간격씩 벌려서 나무들을 배치해주면 나무들을 균등하개 배치할 수 있습니다.

 

각 구간마다 심어야 할 나무의 갯수는 (각 간격)/(간격간의 최대공약수) - 1 이라는 규칙을 가집니다.

1과 3 사이의 간격은 2이고, 이 사이에는 2/2 -1 = 0개의 나무를 배치하면 됩니다.

3과 7 사이의 간격은 4이고, 이 사이에는 4/2 -1 = 1개의 나무를 배치하면 됩니다.

7과 13 사이의 간격은 6이고, 이 사이에는 6/2 -1 = 2개의 나무를 배치하면 됩니다.

 

이를 일반화하면

최종적으로 구하는 나무 사이의 간격은 간격합을 간격들의 최대 공약수로 나눈 값을 간격의 개수만큼 빼주면 됩니다.

---

코드 풀이

gcd() : 최대공약수 구하기 함수

private fun gcd(a: Int, b: Int): Int {
    val r = (a % b)
    return if (r == 0) b else gcd(b, r)
}

두 수의 최대공약수를 구하는 함수입니다. 여기서 입력은 a>=b 여야 합니다.

 

심어야 할 나무 갯수 구하기

fun main() {
    val n = i()
    var lt = i()
    var rt = i()

    var diffSum = rt - lt
    var gcd = diffSum
    var currentDiff: Int
    for (i in 0 until n-2) {
        lt = rt
        rt = i()
        currentDiff = rt - lt
        diffSum += currentDiff
        gcd = if (gcd >= currentDiff) gcd(gcd, currentDiff) else gcd(currentDiff, gcd)
    }
    print(diffSum / gcd - (n - 1))
}

lt는 앞의 나무 위치, rt는 뒤의 나무 위치입니다.

 

매 순간 나무 사이 간격을 currentDiff에 저장하고, 해당 값만큼을 diffSum(간격합)에 합산합니다.

매 순간 나무사이간격의 최대 공약수를 구합니다.

 

이렇게 최종적으로 구해진 나무 사이 간격합을 gcd로 나누고, 간격의 갯수만큼 빼면 됩니다.

 

입출력

private const val S = 65536
private val iS = java.io.DataInputStream(System.`in`)
private val b = ByteArray(S)
private var c = 0
private var l = 0

private fun i(): Int {
    var v = 0
    var c = r()
    do v = v * 10 + c - 48 while (r().also { c = it } > 47)
    return v
}

private fun r(): Byte {
    if (c == l) {
        l = iS.read(b, 0.also { c = it }, S)
        if (l == -1) b[0] = -1
    }
    return b[c++]
}

여기서 r 함수는 바이트 배열을 읽어오고(65536자씩 읽어오고 포인터를 전진시켜가면서 다음 바이트를 반환합니다)

i 함수는 읽은 바이트를 하나씩 읽어가면서 Int를 끊어서 반환합니다.

한번 공백문자 또는 개행이 발생할 때마다 int를 끊어내 구해낼 수 있습니다.

 

이 방식은 바이트 단위로 읽다보니 입력이 매우 빠릅니다.

 

출력의 경우는 표준 입출력을 그대로 사용했습니다.

---

결과

 

108 ms 정도 소요되네요.

---

전체 코드

fun main() {
    val n = i()
    var lt = i()
    var rt = i()

    var diffSum = rt - lt
    var gcd = diffSum
    var currentDiff: Int
    for (i in 0 until n-2) {
        lt = rt
        rt = i()
        currentDiff = rt - lt
        diffSum += currentDiff
        gcd = if (gcd >= currentDiff) gcd(gcd, currentDiff) else gcd(currentDiff, gcd)
    }
    print(diffSum / gcd - (n - 1))
}

private fun gcd(a: Int, b: Int): Int {
    val r = (a % b)
    return if (r == 0) b else gcd(b, r)
}


private const val S = 65536
private val iS = java.io.DataInputStream(System.`in`)
private val b = ByteArray(S)
private var c = 0
private var l = 0

private fun i(): Int {
    var v = 0
    var c = r()
    do v = v * 10 + c - 48 while (r().also { c = it } > 47)
    return v
}

private fun r(): Byte {
    if (c == l) {
        l = iS.read(b, 0.also { c = it }, S)
        if (l == -1) b[0] = -1
    }
    return b[c++]
}