[ 백준 ] 11729 - 하노이 탑 이동 순서

 

하노이 탑 - 재귀문제에서도 정말 유명한 문제

---

핵심은 f(n) 일 경우

* 나머지 f (n-1) 의 탑들이 1번에서 2번으로 가고 

* 남은 f(n) 의 가장 큰 탑이 3번으로 가고

* 그다음에 f(n-1) 의 탑들이 2번에서 3번으로 가야한다.  

 

이처럼 재귀는 f(n) 과 f(n-1) 의 관계를 살펴보는 것이 핵심 

 

 

그리고 answer 나 string builder sb 변수같은 경우에는 main class 안에 static 으로 선언해주었다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int answer =0;
    public static StringBuilder sb = new StringBuilder();
    public static void hanoiTower(int from, int by, int to, int num) {
    answer++;
    if(num == 1) {
        sb.append(from+" "+to).append('\n');
        return;
    }
    else {
        hanoiTower(from, to, by , num-1);
        sb.append(from+" "+to).append('\n');
        hanoiTower(by, from, to , num-1);
    }

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //하노이 탑 이동 순서
        int N = Integer.parseInt(br.readLine());
        // by 변수가
        hanoiTower(1,2, 3, N );

        System.out.println(answer);
        System.out.println(sb);


    }

}

 

좀 어려운 문제였지만 ㅠㅠ 다른 내용 참고를 하며 다행히 잘 풀렸다.