[백준] 11729 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

golang의 fmt 패키지는 기본적으로 buffer를 사용하지 않기 때문에 그냥 출력이나 입력을 하면 느리다고한다. 그냥 출력으로 했더니 시간초과 났다. 아래와 같이 buffer를 사용하게 바꾸니까 맞았다.

 

하노이 탑 개수는 대충 계산해보니까 등비수열 비슷한것 이었다.

내부 함수는 어떻게 진행되는지 찾아서 풀었다.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var out = bufio.NewWriter(os.Stdout)

func hanoi(s, d int, n float64) {
	if n == 1 {
		fmt.Fprintf(out, "%d %d\n", s, d)
		return
	}
	m := 6 - s - d
	hanoi(s, m, n-1)
	hanoi(s, d, 1)
	hanoi(m, d, n-1)
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n float64
	fmt.Fscanf(in, "%f\n", &n)
	fmt.Fprintf(out, "%.0f\n", math.Pow(2.0, n)-1)
	hanoi(1, 3, n)
	out.Flush()
}