프로그래머스[Java] - (Level3)하노이의 탑

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

프로그래머스

코드

class Solution {
  public static int[][] answer;
  public static int x = 0;
    
  // n개를 other기둥을 사용해 from -> to로 옮기기
  public static void hanoi(int n, int from, int other, int to){
      if(n == 0)
          return;
      hanoi(n-1, from, to, other);  // n-1개의 원판을 목적지가 아닌 곳(other)로 옮겨놓음.
      answer[x][0] = from;          // 마지막 원판을 목적지로 옮김.
      answer[x++][1] = to;          // 마지막 원판을 목적지로 옮김.
      hanoi(n-1, other, from, to);  // 목적지가 아닌 곳(other)에 옮겨놓았던 원판들을 목적지로 옮김
  }
    
  public int[][] solution(int n) {
      int num = (int)Math.pow(2, n) - 1;    // 하노이의 이동 횟수: 2^n - 1
      answer = new int[num][2]; // 횟수는 num만큼, 열은 3개(세 개의 기둥)
      hanoi(n, 1, 2, 3);
      return answer;
  }
}

풀이

하노이의탑 이동 횟수는 2^n - 1 이라고 외우고 있었다.

기타 자세한 풀이는 아래 참고

백준 11729번 하노이탑이동순서