문제

전형적인 하노이탑 문제

풀이

n번을 3번 기둥으로 옮기려면 1~n-1번을 2번 기둥으로 옮긴 후 n을 3번 기둥으로 옮길 수 있다.
즉 풀이 순서는
1. n-1개 원판을 기둥 1에서 2로 옮긴다
2. n번 원판을 기둥1에서 기둥 3으로 옮긴다.
3. n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.

1) 함수의 정의
void func(int a, int b, int c) 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수
2) base condition
n=1일때 cout << a<<' '<<b<<'\n';
3) 재귀 식
n-1개의 원판을 기둥 a에서 기둥 6-a-b(a도 b도 아닌 기둥 이게 왜???)로 옮긴다. func(a, 6-a-b, n-1)
n번 원판을 기둥 a에서 b로 옮긴다. cout << a<<' '<<b<<'\n';
n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다. func(6-a-b, b, n-1);

#include <bits/stdc++.h>
using namespace std;

void func(int a, int b, int n){
  if(n == 1){
    cout << a << ' ' << b << '\n';
    return;
  }
  func(a, 6-a-b, n-1);
  cout << a << ' ' << b << '\n';
  func(6-a-b, b, n-1);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int k;
  cin >> k;
  cout << (1<<k) - 1 << '\n'; //(1<<k) == 2^k
  func(1, 3, k);
}

풀이2 - 인자 4개 사용

#include <bits/stdc++.h>
using namespace std;

void hanoi(int n, int start, int to, int bypass) //1 3 2
{
    if(n == 1)
        cout << start<<' '<<to<<'\n';
    else{
        //n-1을 3번을 사용해 2번으로
        hanoi(n-1,start,bypass,to);//1 2 3
        cout << start<<' '<<to<<'\n';
        //2번에 있던 n-1을 1을 사용해 3으로 
        hanoi(n-1,bypass,to,start); // 2 3 1
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1<<num) -1 << "\n";
    hanoi(num,1,3,2);
}