(11729) 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

단계별로 풀어보기

19단계(재귀) 7번째

 

 

 

func(x, y, n)을 x번 장대에 n층 쌓인 탑을 y번 장대로 보내는 함수라고 하자.

이때 나머지 장대을 z번이라고 하면 func(x, y, n)은 세 단계로 나눌 수 있다.

1. x번 장대에 n-1층 쌓인 탑을 z번 장대로 보낸다.

2. x번 장대의 (1에서 쌓고 남은 n번째) 원판을 y번 장대로 보낸다.

3. z번 장대에 n-1층 쌓인 탑을 y번 장대로 보낸다.

여기서 n층 탑의 이동 횟수는 n-1층 탑 이동 횟수의 2배 +1이라는 점화식을 구할 수 있으며,

일반항으로 풀면 이동 횟수는 2^n-1이다.

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  cout << (1<<n)-1 << "\n";
  
  auto func= [&](auto self, int x, int y, int n) -> void {
    if(n==1){
      cout << x << " " << y << "\n";
      return;
    }
    
    int z= 6-x-y;
    
    self(self, x, z, n-1);
    cout << x << " " << y << "\n";
    self(self, z, y, n-1);
  };
  
  func(func, 1, 3, n);
  
  return 0;
}