11790
#include<bits/stdc++.h>
using namespace std;
void hanoi(int x,int start, int end){
if(x==0)return;
hanoi(x-1,start,6-start-end);
cout << start << ' ' << end << '\n';
hanoi(x-1,6-start-end,end);
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
// 1 - 1
// 2 - 3
// 3 - 7
// move count : 2^N-1
cout << (1<<N)-1 << '\n';
hanoi(N,1,3);
}원반의 갯수를 입력받고,
기둥 1에서 기둥 3으로 모든 원판을 옮기는 횟수를 출력해주고,
재귀함수를 통해 그 과정을 출력한다.
먼저, 옮기는 횟수는 중학교 수학시간에 배웠던 $2^k-1$ 이 생각나서 쉬프트연산으로 제곱한 뒤 1 감소시켜 출력해줬다.
재귀함수는 N, start, end 를 인자로 받는다.
N 개의 원판들을 기둥 1에서 3으로 옮기기 위해서는,
N-1 개의 원판들을 6-start-end (start, end 가 아닌 중간 목적지) 으로 옮기고,
N 번째 원판을 end 로 옮긴 뒤, N-1 개의 원판들을 다시 end 로 옮겨야 한다.
base condition 은 N=0 일 때 그냥 리턴하는 것이다.
N==1 일 때 부터 생각해 보면, 그냥 1에서 3으로 옮기면 되니까 다른 재귀함수를 출력하더라도 그냥 return 되니 start(1) 에서 end(3) 으로 옮기는 것을 출력해주면 된다.
N==2 일 때,
먼저 N-1 개의 원판을 중간 목적지로 옮기고 ( hanoi(1,1,2) 호출해서 첫 번재 원판을 1에서 2로 옮김 )
N 번째 원판을 end(2) 로 옮기고
중간 목적지에 있는 N-1 개의 원판을 end 로 옮겼다. ( hanoi(1,2,3) )
N==3 일 때,
2개의 원판을 중간 목적지로 옮기는데,
hanoi(2,1,2) 를 호출할 떄의 관점으로는 end 를 중간지점으로 생각하고 모든 원판을 두 번째 기둥으로 옮기는 것을 알 수 있다.
이제 start 에 있는 3 번째 원판을 end 로 옮기고,
hanoi(2,2,3) 를 호출하는데, 이 때 관점으로는 start 를 중간지점으로 모든 원판을 세 번재 기둥으로 옮긴다는 것을 알 수 있다.
이렇게 재귀함수가 중간지점, 목적지가 계속 바뀌어가면서 호출되며 N 개의 원판이 모두 목적지로 이동할 수 있다.
좀 햇갈리는데, 원판이 한 개일 떄부터 생각해보자.
원판 한 개를 중간지점으로 옮기면, 두 번째 원판위에 올라가게 되고,
세 번째 원판의 관점에서는 두 번재 원판이 올라간 곳이 중간지점이 되고
세 번째 원판위에 두 번째 원판이 올라가고, 이 위치는 네 번째 원판의 관점에서 중간지점이고,
세 번재 원판은 네 번째 원판 위에 올라가게 되는 식으로.. 함수가 호출된다. ok?
