백준 1011번: Fly me to the Alpha Centauri - 상세 풀이
🔍 1. 문제 소개
"Fly me to the Alpha Centauri" 문제는 우주 비행사 우현이 공간 이동 장치를 이용하여 x 지점에서 y 지점으로 이동하는 최소 이동 횟수를 구하는 문제입니다. 공간 이동 장치는 이전 이동 거리 k 광년을 기준으로 k-1, k, k+1 광년만 이동할 수 있습니다. y 지점에 도달하기 직전 이동 거리는 반드시 1 광년이어야 합니다.
💡 2. 문제 해석
문제의 핵심은 최소 이동 횟수를 구하는 것입니다. 단순히 거리를 이동 거리로 나누는 방식으로는 해결할 수 없습니다. 이동 거리는 이전 이동 거리에 제한을 받기 때문입니다. 따라서 이동 거리의 제한을 고려하여 최소 이동 횟수를 계산하는 알고리즘이 필요합니다. 입력값인 x와 y는 모두 비음의 정수이며, x < y 입니다.
🧠 3. 접근 방법
문제를 효율적으로 해결하기 위해 수학적 접근 방식을 사용합니다. x에서 y까지의 거리를 d라고 하면, d를 이동하는 데 필요한 최소 이동 횟수는 d의 제곱근과 밀접한 관련이 있습니다.
- 거리 d가 n²일 경우, 최소 이동 횟수는 2n-1 입니다. (1, 2, 3, ..., n, n, ..., 3, 2, 1 순서로 이동)
- 거리 d가 n²보다 크고 (n+1)²보다 작을 경우, 최소 이동 횟수는 2n 입니다.
따라서, d의 제곱근을 구하고, 그 값을 이용하여 최소 이동 횟수를 계산할 수 있습니다. 이 방법을 이용하면 O(1) 시간 복잡도로 문제를 해결할 수 있습니다.
⚙️ 4. 구현 과정
- 입력으로 x와 y를 받습니다.
- x와 y의 차이(거리 d)를 계산합니다.
- d의 제곱근을 구하고 정수로 변환합니다.
- d가 n²인지, 아니면 n²과 (n+1)² 사이인지 판단하여 최소 이동 횟수를 계산합니다.
- 최소 이동 횟수를 출력합니다.
💻 5. 코드 설명
import kotlin.math.sqrt
import kotlin.math.ceil
fun calculateJumps(dist: Int): Int {
if (dist == 1) return 1
var jumps = 1
while (true) {
val maxDist: Long = if (jumps % 2 == 1) {
val k = (jumps + 1) / 2
k.toLong() * k.toLong()
} else {
val k = jumps / 2
k.toLong() * (k + 1).toLong()
}
if (maxDist >= dist) {
return jumps
}
jumps++
}
}
fun main() {
val t = readLine()!!.toInt()
repeat(t) {
val (x, y) = readLine()!!.split(" ").map { it.toInt() }
val dist = y - x
println(calculateJumps(dist))
}
}
⏱️ 6. 시간 복잡도와 공간 복잡도 분석
시간 복잡도: O(t), t는 테스트 케이스의 개수입니다. 각 테스트 케이스에 대한 계산은 calculateJumps 함수 내에서 O(1) 시간에 수행됩니다. 제곱근 연산은 상수 시간으로 간주됩니다.
공간 복잡도: O(1). 입력값 외에 추가적인 메모리를 사용하지 않습니다.
🎯 7. 결론
이 문제는 수학적 사고와 효율적인 알고리즘 설계 능력을 요구하는 문제였습니다. 제곱근을 이용하여 O(1) 시간 복잡도를 달성함으로써, 매우 효율적으로 문제를 해결할 수 있었습니다. 더 이상의 알고리즘적인 개선은 어렵지만, 코드 가독성을 높이기 위한 추가적인 리팩토링은 가능합니다. 이 문제를 통해 수학적 아이디어를 프로그래밍에 적용하는 방법과 효율적인 알고리즘의 중요성을 다시 한번 확인할 수 있었습니다.