백준 - 11729 : 하노이의 탑(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/11729

 

[문제 설명]

하노이의 탑을 옮겨라.

 

[접근 방법]

법칙이 있을 거라 생각하고 n개와 n - 1개일 때 관계를 생각하며 동적프로그래밍으로 접근했다.

그런데 도저히 못풀겠어서 다른 사람들의 답을 참고해서 풀었다.

참고한 블로그

https://st-lab.tistory.com/96

[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]

재귀로 푸는 웰노운 문제인듯하다.

n개가 있으면 n-1개는 도착점이 아닌 중간 지점에 놓고, 1개는 도착 지점에 놓는 방식으로 놓으면 최소한의 횟수로 움직일 수 있는 듯하다.

 

fun main() {
    val sb = StringBuilder()
    val n = readln().toInt()
    var cnt = 0

    fun hanoi(n: Int, start: Int, mid: Int, end: Int) {
        if (n == 1) {
            sb.append("$start $end\n")
            cnt++
            return
        }

        hanoi(n - 1, start, mid = end, end = mid)
        sb.append("$start $end\n")
        cnt++
        hanoi(n - 1, mid, mid = start, end = end)
    }

    hanoi(n, start = 1, mid = 2, end = 3)
    println("$cnt\n${sb.deleteCharAt(sb.length - 1)}")
}