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

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

11729번: 하노이 탑 이동 순서

하노이탑 이동 횟수는

A(n)=A(n-1)+A(n-1)+1 번이다.

이 수열을 풀어보면

A(n)=2^n - 1 번이다.

 

하노이 탑을 a에서 c로 이동하고자 할 때

N-1개를 a에서 b로 이동을 하고,

1개를 a에서 c로 이동하고,

N-1개를 b에서 c로 이동을 하면 이동이 끝난다.

 

 

코드

import java.util.*;

public class back11729 {

    public static StringBuilder sb=new StringBuilder();

    public static void main(String args[]){

        Scanner scanner=new Scanner(System.in);

        int num=scanner.nextInt();

        sb.append((int)(Math.pow(2,num)-1)).append('\n');

        Hanoi(num,1,2,3);

        System.out.println(sb);

    }

    public static void Hanoi(int num, int a, int b, int c){

        if(num==1){

            sb.append(a+" "+c+"\n");

            return;

        }

        Hanoi(num-1, a, c, b);

        sb.append(a+" "+c+"\n");

        Hanoi(num-1, b, a, c);

    }

}