[백준/JAVA] 11729번: 하노이 탑 이동 순서

🔺 문제

11729번: 하노이 탑 이동 순서

 

🔺 코드

import java.util.*;
import java.io.*;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		sb.append((int) (Math.pow(2, n) - 1)).append("\n");
		
		Hanoi(n, 1, 2, 3);		
		System.out.println(sb);	
	}
	
	//                                 출발지   경유지  목적지
	public static void Hanoi(int n, int from, int via, int to) {
	    if(n == 1) {
	        sb.append(from + " " + to + "\n");
	        return;
	    }
	    	    
	    // 1) n-1개를 A→B로 이동
	    Hanoi(n-1, from, to, via);
	    
	    // 2) 1개를 A→C로 이동
	    sb.append(from + " " + to + "\n");
	    
	    // 3) n-1개를 B→C로 이동
	    Hanoi(n-1, via, from, to);
	}
}

✅ 해결 아이디어
- 규칙을 찾아 점화식 구하기!
- 최소 단위에 대한 조건!

복습해야지..ㅠ

---

🔺 다른 풀이들

[백준 알고리즘][자바] 11729번 : 하노이 탑 이동 순서

비슷한데 cnt를 직접 구하신...

 

---

(참고)

- 풀이

[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]

하노이의 탑 - 위키백과, 우리 모두의 백과사전