BOJ 11729 - 하노이 탑 이동 순서

문제

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

 

 

풀이

재귀를 이용해 문제를 해결한다

1. 가장 큰 원판 n은 맨 밑에 있어야 하므로 n-1개를 첫 번째 장대에서 두 번째 장대로 옮긴다

2. 원판 n을 첫 번째 장대에서 세 번째 장대로 옮긴다

3. 원판 n-1개를 두 번째 장대에서 세 번째 장대로 옮긴다

 

원판을 옮겨야 하는 총 횟수는  2ⁿ-1 이다

재귀함수에서 2ⁿ으로 자기 자신을 호출하고 n == 1일 때 한 번만 호출하므로 -1을 해준다

 

 

코드

python

def hanoi(n, src, aux, dest):
    if n == 1:
        print(src, dest)
    else:
        hanoi(n - 1, src, dest, aux)
        print(src, dest)
        hanoi(n - 1, aux, src, dest)
 
 
n = int(input())
 
print(2**n - 1)
hanoi(n, 1, 2, 3)

 

C++

#include <iostream>
 
using namespace std;
 
void func(int a, int b, int n)
{
    if (n==0) return;
    func(a, 6-a-b, n-1);
    cout << a << ' ' << b << '\n';
    func(6-a-b, b, n-1);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    int n;
    cin >> n;
    cout << (1 << n) - 1 << '\n';
    func(1, 3, n);
 
 
    return 0;
}