baekjoon 1914. 하노이 탑

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

문제

원반의 개수가 주어질 때 최소 이동 순서와 이동 방법을 출력하라.
in : 3
out :
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

풀이

import java.util.Scanner;

public class Main {
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        StringBuilder sb = new StringBuilder();
        q1914HanoiTower(n, '1', '2', '3', sb);
        System.out.println(count);
        System.out.println(sb);
    }

    public static void q1914HanoiTower(int n, char from, char mid, char to, StringBuilder sb) {
        count++;
        if (n == 1) {
            sb.append(from + " " + to + "\n");
            return;
        }
        q1914HanoiTower(n - 1, from, to, mid, sb);
        sb.append(from + " " + to + "\n");
        q1914HanoiTower(n - 1, mid, from, to, sb);
    }
}

1. 원반이 한 개 라면, 바로 옮기면 됩니다.
2. 원반이 n 개라면, n번째 원반을 옮기기 위해 n-1 개의 원반을 mid(경유지) 로 옮겨야 합니다.
3. n-1을 중간으로 옮기고 n을 목적지로 옮깁니다.
4. 중간에 있는 n-1을 목적지로 옮겨야 합니다.

count는 Math.pow(2, N) - 1 이라고 합니다만, 수식 유추를 못해서 별도 static 변수 count를 사용했습니다.

근데 뭐 저 코드 메모리 초과 나옵니다. 다른 분도 저와 유사하게 푸신 분이 있던데 마찬가지로 메모리 초과 나옵니다.

Stack을 활용해서 풀고 싶었으나, 정답을 봐도 전혀 모르겠습니다. 어떻게 저런 순서로 stack에 넣어야 하는지 하나도 모르겠습니다. -_-