[JAVA] 백준 11729번

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

11729번: 하노이 탑 이동 순서

 

💡 가장 작은 단위에서부터 시작해서 큰 단위가 어떻게 움직이는지를 캐치하는 것이 관건!

 

문제 해결 과정

1. 점화식을 통해 원판을 옮길 횟수를 계산

   -> 2^n - 1

 

 

2. 원판 N개 중 맨 아래 (가장 큰) 원판을 C로 옮기기 위해서는 나머지(N-1)개의 원판을 B로 이동시켜야 한다. (N-1번 동작)

 

3. 그 후 맨 아래에 있던 원판을 C로 이동시킨다. (1번 동작)

 

4. B에 있던 나머지(N-1)개의 원판을 C로 이동시킨다. (N-1번 동작)

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
 
    static int N;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        // 점화식으로 횟수 계산
        sb.append((int) Math.pow(2, N)-1 + "\n");
        hanoi(N, 1, 2, 3);
        
        System.out.println(sb);
    }
    
/*    cnt : 옮길 원판의 개수
    from : 출발지 (시작 기둥)
    tmp : 경유지 (중간 기둥)
    to : 목적지 (도착 기둥)  */
    
    static void hanoi(int cnt, int from, int tmp, int to) {
        
        // 기저 조건 (더이상 옮길 원판 없음)
        if(cnt==0) return;
        
        // 1. 원판을 출발지에서 경유지로 이동
        hanoi(cnt-1, from, to, tmp);
        
        // 2. 원판을 출발지에서 목적지로 이동 (한번 동작)
        sb.append(from + " " + to + "\n");
 
        // 3. 원판을 경유지에서 목적지로 이동
        hanoi(cnt-1, tmp, from, to);
    }
 
}