문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

코드

// T(n) == 2^n - 1 == n개의 원판이 최소한의 이동으로 3번까지 가는 횟수
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(2);
    }
}

class Solution {
    int[][] answer;
    int count;

    public int[][] solution(int n) {
        answer = new int[(int) Math.pow(2, n) - 1][2];
        count = 0;
        hanoi(n, 1, 3, 2);
        return answer;
    }

    public void hanoi(int n, int from, int to, int via) {
        if (n == 1) {
            answer[count] = new int[]{from, to};
            count++;
            return;
        }

        // n-1개의 원반을 via 기둥으로 이동
        hanoi(n - 1, from, via, to);

        // 가장 큰 원반을 to 기둥으로 이동
        answer[count] = new int[]{from, to};
        count++;

        // n-1개의 원반을 to 기둥으로 이동
        hanoi(n - 1, via, to, from);
    }
}

생각

일단 구글검색을 안할 수 없었다. 내가 알고 있는 하노이의 탑 지식은 원판 개수가 짝수인지 홀수인지에 따라 첫번째 이동이 2번으로 가는지 3번으로 가는지 밖에 없었기 때문에 최소 횟수에 대한 수학식이 있는지 검색했다. 배열의 크기를 정해서 메모리를 아껴보기 위해서이다.

수학식과 원래 알고 있던 정보를 기반으로 코드를 작성해 보았다.