하노이의 탑

#define _CRT_SECURE_NO_WARNINGS //경고 제거
#include <stdio.h>
#include <math.h>
/*
from: 출발막대
  by: 거쳐갈 막대(잠시 원판 보관할 막대)
  to: 목표막대
  n: 원판 개수
*/
void hanoi(int n, int from, int by, int to) {
	if (n == 0)
		return;
	else {
		hanoi(n - 1, from, to, by); //원판 맨밑에 1개 빼고 나머지 n-1개 거쳐갈 막대(2번째)로 옮기기
		printf("%d %d\n", from, to); //맨밑 원판을 목표 막대(3번째)로 옮기기
		hanoi(n - 1, by, from, to); //2번째 막대에 있는 원판들 목표막대(3번째)로 모두 옮기기
	}

}

int main() {
	int N;
	scanf("%d", &N);
	int k = pow(2,N) - 1; //최소한으로 이동 횟수: 2^N -1
	printf("%d\n", k);
	hanoi(N, 1, 2, 3); 
	/* 출발 막대: 1
	   거쳐갈 막대: 2
	   목표 막대: 3
	*/
	return 0;
}