시작

이 문제는 생각보다 유명한 문제다. 그렇다면 어떻게 푸는지 한번 생각해보자. 우선 예외 조건을 먼저 보자면

예외 조건

1. 한번에 한 개의 원반만 이동 가능
2. 쌓아 놓은 원판은 무조건 아래의 것이 위에 것보다 커야됨

우선 예제 입력을 보자면 최소 7번을 옮겨야 3번 탑으로 옮길 수 있다는 것을 알 수 있는데, 그 이유는 하노이의 탑 문제에서 나오는 "최소"의 공식은 2^n-1이기 때문에 최소 7번을 옮길 수 있다는 것을 알 수 있다.

예제 옮기는 순서

1. 1번탑 -> 3번탑
2. 1번탑 -> 2번탑
3. 3번탑 -> 2번탑
4. 1번탑 -> 3번탑
5. 2번탑 -> 1번탑
6. 2번탑 -> 3번탑
7. 1번탑 -> 3번탑

이런식으로 7번을 옮길 수 있는데, 어떤 사람은 물어볼것이다. "그냥 1번에서 2번으로 역순으로 옮긴 후 3번으로 옮기는건 안되나요?" 라는 사람은 문제를 다시 봐야 될 것이다. 문제중 조건에 "쌓아 놓은 원판은 무조건 아래의 것이 위에 것보다 커야됨" 이라는 조건을 만족시키지 못하기 때문에 틀린 답이 될 수 있다.
그렇기에 한번 간단하게 알고리즘을 설명하자면

알고리즘

1. 가장 큰 원반을 제외 하고 중간으로 옮긴다.
2. 중간 기둥에 있는 원반을 마지막 기둥으로 옮긴다

코드

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

using namespace std;

int n;

void Move(int from, int to) {
	cout << from << " " << to << "\n"; 
}

/*
n = 원판의 개수
from = 현재 위치
by = 중간  기둥 번호
to = 마지막 기둥 번호
*/
void hanoi(int n, int from, int by, int to) {
	if (n == 0) return;
	hanoi(n - 1, from, to, by);
	Move(from, to);
	hanoi(n - 1, by, from, to);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	// 최소 이동 횟수는 2^n - 1
	cout << (int)(pow(2, n) - 1) << "\n";
	hanoi(n, 1, 2, 3);
}