재귀의 동작 자체는 이해가 된다 메서드를 호출할때마다 콜스택에 쌓이고, 스택은 후입선출이니까 마지막에 들어온 순서부터 리턴한다 알겠는데

하노이 탑을 도당체 재귀로 풀 생각은 어떻게 드는건지 모르겠다...


문제를 읽고, 아 이거 재귀네 ㅋ 하고 재귀호출 설계를 어떻게 하냐


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

public class Main {
    public static StringBuilder sb = new StringBuilder();

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

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

        String s = br.readLine();

        StringTokenizer st = new StringTokenizer(s, " ");
        int n = Integer.parseInt(st.nextToken());
        sb.append((1 << n) - 1).append("\n");
        solution(1, 3, n);
        System.out.println(sb);
    }

    public static void solution(int src, int dest, int n) {
        if (n == 1) {
            sb.append(src).append(" ").append(dest).append("\n");
            return;
        }

        solution(src, 6-src-dest, n-1);
        sb.append(src).append(" ").append(dest).append("\n");
        solution(6-src-dest, dest, n-1);
    }
}

n개의 원반이 있을때 1에서 n만큼 왼쪽 시프트 연산하고 1을 빼면 n개의 원반이 총 이동하는 수인걸 도대체 어떻게 알아낸걸까

그리고 6-src-dest 라는 저 식은 도대체 어떻게 알게된걸까? 기둥이 3개 있으니까 1+2+3에서 출발지기둥과 목적지기둥을 빼면 n-1번째의 출발지와 목적지가 나온대

내 눈엔 지금 마법을 부린것 같다 대체 뭐냐

학교다닐때 수학좀 열심히 할껄 ㅅㅂ