문제

11729 하노이 탑 이동 순서

풀이

개념

이미지 원본

요약

즉, 디스크의 수가 n개일 때,

• step 1: move n-1 disk "from" --> "by" (재귀)
• step 2: move last disk "from" --> "to"
• step 3: move last disk "from" --> "to" (재귀)

답

1. kotlin code: timeout 발생 버전

• 출력 line이 많아 매번 출력을 하면 io 때문에 시간이 길어진다.

import kotlin.math.pow

fun main() {
    val n = readln().toInt()
    
    println((2.0.pow(n) - 1).toInt())
    hanoi(n, 1, 2, 3)
}

fun hanoi(n: Int, from: Int, by: Int, to: Int):Unit = when(n) {
    1 -> println("$from $to")
    else -> {
        hanoi(n-1, from, to, by)
        println("$from $to")
        hanoi(n-1, by, from, to)
    }
}

2. kotlin code: 최종

• StringBuilder 타입 변수에 output값을 담아두고 한 번에 출력한다.

import kotlin.math.pow

fun main() {
    val n = readln().toInt()
    println((2.0.pow(n) - 1).toInt())
    println(hanoi(n, 1, 2, 3))
}

fun hanoi(n: Int, from: Int, by: Int, to: Int):StringBuilder = when(n) {
    1 -> StringBuilder().append(from).append(' ').append(to).append('\n')
    else -> {
        hanoi(n-1, from, to, by)
            .append(from).append(' ').append(to).append('\n')
            .append(hanoi(n-1, by, from, to))
    }
}