백준 - 1914

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

풀이

장대를 1,2,3 번으로 두고,원판 수가 n일 때, n-1개가
있다고 생각하고 3번 장대로 보내는 것을 목표로 생각한다.
n번째 원판은 n-1번째 원판이 중간 경로인 2번 장대를 거쳐야 3번째 장대에 갈 수 있다는 법칙이 공식을 이해하는데 중요한 점이다.

예시로 원판이 3개 일때, 3개의 -1개인 2개,
2개의 -1개인 1개를 먼저 생각한다.

1.(1)번 원판을 3번째로 보낸다.
2.(2)번 원판은 (1)번이 3번째에 있기 때문에 2번째 장대로 간 다음
3.3번째 장대를 비우기 위해서 (1)번 원판을 (2)번원판위로 (2번째 장대)로 보낸다.
4.(3)번 원판은 3번째 장대로 그리고 (1),(2)원판을 3번째 장대로 보낸다.

위 과정으로 공식을 만들면 수행과정의 수는 2ⁿ-1가 된다.

코드

import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;

class Main{
    public static void main(String[] args){
        int N;
        Scanner sc = new Scanner(System.in); //입력
        N = sc.nextInt();
        BigInteger count =  BigInteger.valueOf(2).pow(N).subtract(BigInteger.ONE); //메모리 초과방지를 위해 범위 설정

        System.out.println(count);//수행 횟수는 한번만 출력
if(N<=20){ //N이 20보다 작을 때만 과정 출력
hanoi(N,1,2,3);
}
    }
    public static void hanoi(int num,int start,int middle,int end){

        if(num < 1){return;}
        hanoi(num-1,start,end,middle);
            System.out.println(start + " " + end); //n-1의 과정
        hanoi(num-1,middle,start,end);
    }
}

참조

이미지 참조 링크

참고 강의 영상
참고 영상 링크