하노이 탑과 재귀

알아두면 좋은 점은 아래와 같다.

1. 모든 기둥은 항상 규칙을 준수한다.
2. 목적은 자신을 목적지로 옮기고 싶어하고 그러기 위해 자신 위에 있는걸 목적지가 아닌 빈 곳으로 옮긴다.

시간 복잡도는 2^n 인데 재귀적으로 두 번 호출해서 그렇다고 생각하면 좋다.
세세하게는 점화식을 세워서 구할 수 있는데 스킵

하노이 탑이 유명하고 재귀공부할땐 필수적이지만 기억이 안나면 힘들다..

하노이 탑 이동경로

int rec(int from, int to, int val) {
    if (val == 1) {
        System.out.println("" + from + " " + to + "\n");
        return 1;
    }
    int empty = 6 - from - to;
    rec(from, empty, val - 1);
    System.out.println("" + from + " " + to + "\n");
    rec(empty, to, val - 1);
}

하노이 탑 특정 turn 에서 각 기둥의 합 구하기

static int[] pillarSum = new int[4];
    static int cur = 0;
    static void rec(int from, int to, int val, int target) throws Exception {
        if (val == 1) {            
            pillarSum[from] -= val;
            pillarSum[to] += val;
            cur++;
            if (cur == target) {
                System.out.println("" + pillarSum[1] + " " + pillarSum[2] + " " + pillarSum[3]);
                return;
            }
            return;
        }
        int nextEmpty = 6 - from - to;
        rec(from, nextEmpty, val - 1, target);
        pillarSum[from] -= val;
        pillarSum[to] += val;
        cur++;
        if (cur == target) {
            System.out.println("" + pillarSum[1] + " " + pillarSum[2] + " " + pillarSum[3]);
            return;
        }
        rec(nextEmpty, to, val - 1, target);
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int t = Integer.parseInt(br.readLine());
  
        for (int i = 1; i <= n; i++) {
            pillarSum[1] += i;
        }
        if (n <= 20) {
            rec(1, 3, n, t);
        }
    }
}

재귀를 잘하면 DP 에도 도움이 되니 이쪽도 공부를 해야겠다..