구현방법

하노이의 탑 규칙은 n개의 원판을 src에서 dst으로 이동할려면
n-1개의 원판을 src에서 6 - src - dst로 이동한다 -> 1개의 원판을 src에서 dst으로 이동한다 -> n-1개의 원판을 6 - src - dst에서 dst으로 이동한다
3가지로 요악할 수 있다.
이때 1번째와 3번째에서 6 - src - dst로 해줘야 src위치와 dst위치를 제외한 위치를 얻을 수 있다. ex(6 - 1 - 3 = 2)
함수를 2개 만든 이유는 마지막에 총 움직인 횟수를 출력하면 상관없지만 처음에 출력해야하기 때문에 횟수를 세는 함수와 수행과정을 출력하는 함수 2개를 만들었다.

정답

#include <stdio.h>

int getNumberOfHanoi(int n, int src, int dst) {
  if (n == 1) {
    return 1;
  }
  return getNumberOfHanoi(n - 1, src, 6 - src - dst) + getNumberOfHanoi(1, src, dst) + getNumberOfHanoi(n - 1, 6 - src - dst, dst);
}

int hanoi(int n, int src, int dst) {
  if (n == 1) {
    printf("%d %d\n", src, dst);
    return 1;
  }
  return hanoi(n - 1, src, 6 - src - dst) + hanoi(1, src, dst) + hanoi(n - 1, 6 - src - dst, dst);
}

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