Kotlin 코틀린 백준 25344 행성 정렬

문제

행성 정렬은 행성들이 일직선으로 정렬된 것처럼 보이는 현상이다. 최근 지구에서도 18년 만에 행성 정렬을 관측할 수 있었다.

평행세계의 준서가 살고 있는 지구에서는 $N$개의 행성을 관측할 수 있다. 준서는 얼마나 기다려야 $N$개의 행성이 일렬로 나열되는 순간을 볼 수 있을지 궁금해졌다.

하늘을 열심히 관찰한 결과, 준서는 다음 사실들을 알 수 있었다.

•  𝑁개의 행성이 일렬로 나열되는 순간이 존재한다.
• 행성 정렬의 주기는 $10^{9}$초 이하이다.
• 1, 2, 3번째 행성은 $T_1$초마다 일렬로 나열된다.
•  2, 3, 4번째 행성은 $T_2$초마다 일렬로 나열된다.
• ...
• $N-2, N-1, N$번째 행성은 $T_{N-2}$초마다 일렬로 나열된다.

준서를 위해 행성 정렬의 주기를 구해주자.

 

입력

첫째 줄에 정렬되길 바라는 행성의 개수 $N$이 주어진다. ($3 \leq N \leq 100\,000$)

둘째 줄에 행성이 일렬로 나열되는 주기를 나타내는 정수 $T_1, T_2, \cdots, T_{N-2}$가 공백으로 구분되어 주어진다. ($1 \leq T_i \leq 100\,000$)

 

출력

행성 정렬의 주기를 출력한다. 행성 정렬의 주기는 $10^9$초 이하이다.

---

문제 풀이

모든 행성 정렬 주기의 최소 공배수를 구해주면 된다.

행성 정렬의 주기가 $10^9$초 이하라는 조건이 있으므로 Int대신 Long을 사용하는 것이 좋다.

 

최대 공약수(GCD) 구하기

최소 공배수(LCM)를 구하기 위해서는 최대 공약수(GCD)가 필요하다.

최대 공약수를 간단하게 구하는 방법으로는 '유클리드 호제법'이 있다.

 

두 수의 나머지가 0이 나올 떄 까지 계속 재귀함수를 돌려주면 된다!

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

 

최소 공배수(LCM) 구하기

최대 공약수로 최소 공배수를 만들려면,

두 수의 곱에 최대 공약수를 나누면 된다.

private fun lcm(a: Long, b: Long): Long {
    return a * b / gcd(a, b)
}

 

코드

/**
 * 행성 정렬
 * https://www.acmicpc.net/problem/25344
 */

private var n = 0
private var list = listOf<Long>()

private fun solution() {
    var lcm = list[0]

    for (i in 1 until list.size) {
        lcm = lcm * list[i] / gcd(lcm, list[i])
    }

    println(lcm)
}

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

private fun input() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    list = readLine().split(" ").map { it.toLong() }
    close()
}

fun main() {
    input()
    solution()
}

 

Reference

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

https://adjh54.tistory.com/179

[Java/알고리즘] 유클리드 호제법(Euclidean Algorithm) : 최대공약수, 최소공배수