[BOJ][KOTLIN] 11729 하노이 탑 이동 순서

[BOJ][KOTLIN] 11729 하노이 탑 이동 순서

풀이

기둥 세개를 시작, 중간, 끝 위치로 설정한다. 3개의 탑을 옮길때 1, 2 를 하나의 묶음으로 생각하고 N = 2 와 동일한 이동으로 생각한다. 2번 과정을 통해서 아래와 같은 알고리즘 규칙을 도출 한다.

hanoi(N - 1, start, mid, end) // N - 1 개의 원탑을 끝 기둥을 이용하여 중간 기둥으로 이동

hanoi(1, start, end, mid) // 1개의 원탑을 끝 기둥으로 이동

hanoi(N - 1, mid, end, start) // 첫번째에서 이동된 N - 1 원탑을 중간 기둥에서 시작 기둥을 이용하여 끝 기둥으로 이동

import java.io.* var count = 0 var result = mutableListOf() fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val bw = BufferedWriter(OutputStreamWriter(System.out)) val N = br.readLine().toInt() hanoi(N, 1, 3, 2) bw.write("${count}

") for (res in result) { bw.write("${res}

") } bw.flush() bw.close() br.close() } private fun hanoi(N: Int, start: Int, end: Int, mid: Int) { if (N == 1) { count++ result.add("$start $end") } else { hanoi(N - 1, start, mid, end) hanoi(1, start, end, mid) hanoi(N - 1, mid, end, start) } }

from http://jefflim-81.tistory.com/35 by ccl(A) rewrite - 2021-11-21 17:01:25