[1914번] 하노이 탑

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 하노이 탑

하노이 탑 방식은 막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성할 수 있다.

1. 작은 원반 n-1개를(맨 아래의 원반을 제외한 나머지 원반) A에서 B로 이동

2. 큰 원반(맨 아래의 원반) 1개를 A에서 C로 이동

3. 작은 원반(위의 1단계에서 옮겨진 원반) n-1개를 B에서 C로 이동시키면 된다.

이것을 코드로 표현하면 아래 hanoi 코드와 같게 된다.

one :: from(에서 시작하여)

two :: by(를 거쳐서)

three :: to(로)로 생각하면 생각하기 조금 더 쉬울 것 같다.

그리고 하노이 타워의 이동 수를 구하는 방법은

공식을 이용하자.

하노이 탑에서 원판이 N개일때 총 횟수 :: 

소스 코드 : 

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    
    static void hanoi(int num, char one, char two, char three)
    {
        if(num == 1)
            System.out.println(one + " " + three);
        
        else
        {
            hanoi(num - 1, one, three, two);
            System.out.println(one + " " + three);
            hanoi(num - 1, two, one, three);
        }
        
    }  
    
    public static void main(String[] args)
    {
        BigInteger c = new BigInteger("2");
        Scanner sc = new Scanner(System.in);
               
        int n = sc.nextInt();
        
        c = c.pow(n).subtract(BigInteger.ONE);
        
        System.out.println(c);
        
        if(n <= 20)
            hanoi(n,'1','2','3');
    }
    
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>