백준 - 11729 : 하노이의 탑(Kotlin)
본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
https://github.com/ROUTINE-STUDY/Algorithm
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.
GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능
초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub.
github.com
문의는 댓글 바람.
문제 출처 :https://www.acmicpc.net/problem/11729
[문제 설명]
하노이의 탑을 옮겨라.
[접근 방법]
법칙이 있을 거라 생각하고 n개와 n - 1개일 때 관계를 생각하며 동적프로그래밍으로 접근했다.
그런데 도저히 못풀겠어서 다른 사람들의 답을 참고해서 풀었다.
참고한 블로그
[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]
www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이
st-lab.tistory.com
재귀로 푸는 웰노운 문제인듯하다.
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)}")
}