[재귀] C11 백준 11729 하노이 탑 이동 순서 풀이

문제

• 11729

풀이 과정

• 하노이탑 테스트 링크
• 하노이탑의 일반항은 2^n-1 -> 총 이동 횟수
• 하노이탑 재귀 조건
  • a는 b로 이동해야 함 (그러기 위해서는 a-1 -> c로 이동)
  • 이 후 a-1 원반들을 b로 이동

#include <stdio.h>

void hanoi(int n, int a, int b, int c) {
    if (n == 1) {
        printf("%d %d\n", a, b);
        return;
    }
    
    hanoi(n-1, a, c, b);
    printf("%d %d\n", a, b);
    hanoi(n-1, c, b, a);
}

int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d\n", (1 << n) - 1);
    hanoi(n, 1, 3, 2);
    return 0;
}