[C++] [CSES] Tower of Hanoi (Introductory Problems)

CSES의 열 네번째 문제입니다.

하노이의 탑은 재귀 개념을 배울 때 항상 배우는 것인데, 재귀라는 것이 굉장히 신기하고 멋지다는 것을 알 수 있는 문제였습니다.

 

Task

The Tower of Hanoi game consists of three stacks (left, middle and right) and n round disks of different sizes. Initially, the left stack has all the disks, in increasing order of size from top to bottom.

The goal is to move all the disks to the right stack using the middle stack. On each move you can move the uppermost disk from a stack to another stack. In addition, it is not allowed to place a larger disk on a smaller disk.

Your task is to find a solution that minimizes the number of moves.

Input

The only input line has an integer n: the number of disks.

Output

First print an integer k: the minimum number of moves.

After this, print k lines that describe the moves. Each line has two integers a and b: you move a disk from stack a to stack b.

Constraints

• 1≤n≤16

Example

Input:
2

Output:
3
1 2
1 3
2 3

 

Code

#include<bits/stdc++.h>
using namespace std;
int n;
void hanoi(int n, int s, int e, int m){
    if (n == 0) return;
    hanoi(n-1, s, m, e);
    cout << s << " " << e << "\n";
    hanoi(n-1, m, e, s);
}
int main(){
    cin >> n;
    cout << pow(2, n) - 1 << "\n";
    hanoi(n, 1, 3, 2);
}

생각해야 하는 것

• 저 hanoi라는 함수를 잘 정의해놓고 알아서 굴러가게 만드는 것을 이해하는 것이 중요하다고 생각합니다.
• hanoi 함수는 s 부분에 n 개의 벽을 e까지 옮기는 함수입니다. 만약 아무것도 없다면(n = 0) 바로 함수를 종료합니다.
• n 이 1 이상 있다면 n-1개를 m 부분으로 옮긴 다음 가장 밑에 있는 디스크를 e로 옮긴 다음 m으로 옮겼던 n-1개의 디스크를 다시 e로 옮겨야 합니다.
• 총 몇번을 옮겨야 하는지 알기 위해서는 hanoi(n)을 호출했을 때 어떤 함수들이 호출되는지 알아야 합니다. 
• n 1번--> (n-1) 2번 --> (n-2) 2^2번 ---> .... ---> (0) 2^n번
• 여기서 hanoi(0)이 호출되었을 때 아무것도 출력하지 않기 때문에 총 옮기는 횟수는 1 + 2^1 + 2^2 + ... + 2^(n-1) 입니다.
• 등비수열의 합 공식을 이용하면 합은 2^n - 1입니다.