[백준 1914] 하노이 탑

 

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

1914번: 하노이 탑

 

예를 들어 원판의 개수 N이 3이라면 아래와 같이 총 7번의 옮김이 필요하다.

위의 그림을 생각하며 포인트를 잡자면,
・ 장대1에 있는 마지막 1개의 원판을 장대3으로 옮겨야 한다.
・ 그럼 장대1에 있는 K-1개의 원판을 중간 기둥으로 옮겨야 한다.
・ 마지막으로 장대2로 옮겨놨던 K-1개의 원판을 다시 장대3으로 옮긴다.

"하노이 타워의 원판 이동 횟수" 라고 검색을 하면, 공식은 2^K - 1
코드로 나타내면 아래와 같다.

BigInteger bi = new BigInteger("2");
BigInteger a = bi.pow(K).subtract(BigInteger.ONE);

import java.math.BigInteger;
import java.util.Scanner;

// 1914번 : 하노이 탑
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        
        BigInteger bi = new BigInteger("2");
        BigInteger result = bi.pow(k).subtract(BigInteger.ONE);
        System.out.println(result);

        if (k<=20) { // n이 20 이하일 때만 하노이 탑 이동 과정 출력
            hanoi(k, 1, 2, 3);
        }    
    }

    // 하노이 탑 이동 순서 출력하는 메소드
    static void hanoi(int k, int start, int mid, int end) {
        if (k==1) {
            System.out.println(start + " " + end);
            return;
        }
        hanoi(k-1, start, end, mid);
        System.out.println(start + " " + end);
        hanoi(k-1, mid, start, end);
    }
}

---