백준 - 11729 하노이 탑 이동 순서 풀이

05 Jun 2022

Reading time ~1 minute

문제

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))
    }
}

Attachments

이미지 원본