백준 Java_11729

import java.util.Scanner;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
 
public class Main {
 
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
 
		int N = in.nextInt();
 
		bw.write((int) (Math.pow(2, N) - 1) + "\n");
 
		Hanoi(N, 1, 2, 3);
		bw.flush();
		bw.close();
 
	}
 
	/*
		N : 원판의 개수 
		start : 출발지 
		mid : 옮기기 위해 이동해야 장소 
		to : 목적지
	 */
 
	public static void Hanoi(int N, int start, int mid, int to) throws IOException {
		// 이동할 원반의 수가 1개라면?
		if (N == 1) {
			bw.write(start + " " + to + "\n");
			return;
		}
 
		// A -> C로 옮긴다고 가정할 떄,
		// STEP 1 : N-1개를 A에서 B로 이동 (= start 지점의 N-1개의 원판을 mid 지점으로 옮긴다.)
		Hanoi(N - 1, start, to, mid);
    
		// STEP 2 : 1개를 A에서 C로 이동 (= start 지점의 N번째 원판을 to지점으로 옮긴다.)
		bw.write(start + " " + to + "\n");
    
		// STEP 3 : N-1개를 B에서 C로 이동 (= mid 지점의 N-1개의 원판을 to 지점으로 옮긴다.)
		Hanoi(N - 1, mid, start, to);
 
	}
}

• 작은 원판 위에 큰 원판은 올 수 없다

1. 가장 큰 원판을 C 로 옮기기 위해서는 n-1 개의 원판이 A 에서 B 로 가야한다.
2. 그리고 A 에 있는 가장 큰 원판이 C로 이동할 것이다.
3. B 에 있는 (n-1)개의 원판을 C 로 이동한다.

𝑎𝑛+1 의 경우를 보면,

1. 가장 큰 𝑛 번째 원판을 옮기기 위해 𝑛-1 개의 원판을 옮겨야 한다. 이 때 𝑛 개의 원판이 A 에서 B 로 이동하는 경우는 𝑎𝑛-1 이다.

2. 𝑛 번째 원판을 A 에서 C 로 옮기는 경우는 1 이다.

3. B에 있는 n개의 원판이 C로 옮기는 경우는 𝑎𝑛-1 이다.

점화식은 *𝑎𝑛 = 2×𝑎𝑛 - 1 + 1 ⇒ 𝑎𝑛 = 2n- 1*

재귀를 통해 가장 작은 단위로 들어간다.

A 에서 B로 이동하는 함수를 재귀호출하여 이동해야 할 원판이 1개가 되면 그 때 A 에서 B로 이동했다는 것을 출력한 뒤, 함수를 리턴하면 된다.

그렇게 원판이 1개일 때 A 에서 B로 이동한 함수가 닫히면

그 전 단계 재귀로 다시 돌아오면 원판이 2개일 때가 된다. 이때는 앞서 그림에서 봤듯이 1개의 원판이 A 에서 C로 이동하면 되므로, 이 때의 경우를 출력한다.

출력이 끝나면, B 에서 C 로 이동하도록 다시 재귀호출을 한다.

move(3, start, end, sub);

->	move(2, start, sub, end);
     ->	move(1, start, end, sub);
        print(start + " -> " + sub);
     -> move(1, end, sub, start);
        
    print(start + " -> " + end);
    
->    move(2, sub, end, start);
     ->	move(1, sub, start, end);
        print(start + " -> " + end);
     -> move(1, start, end, start);

참조 : https://iseunghan.tistory.com/214
https://st-lab.tistory.com/96