하노이 탑 K번째 찾기

하노이 탑에 N개의 원반이 있을 때 K번째에는 어떻게 하노이 탑이 구성되어 있는지 찾는 알고리즘이다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
void hanoi(int arr[], int n, long long k, int s, int e)
{
    long long mid = 1ll << (n - 1);
 
    if (n == 0)
        return;
 
    if (k < mid)
    {
        arr[n - 1] = s;
        hanoi(arr, n - 1, k, s, 6 - s - e);
    }
    else
    {
        arr[n - 1] = e;
        hanoi(arr, n - 1, k - mid, 6 - s - e, e);
    }
}
 
int main()
{
    // n개의 원판이 있을 때 k번째 상황 구하기
    int *arr;
    int n, k; 
    cin >> n >> k;
 
    arr = new int[n];
 
    for (int i = 0; i < n; i++)
        arr[i] = 1;
    hanoi(arr, n, k, 1, 3);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    return 0;
}

원리는 다음과 같다.

A B C 세개의 원반을 놓을 수 있는 공간이 있을 때, A에 모든 원반이 있다 생각하자.

우리는 n번째 원반을 C로 옮겨야 하니 n - 1번째 까지를 A에서 B로 옮겨야 한다.

그 후 A에 있던 C 원반을 옮길 수 있게 된다.

그다음 B에 있는 n - 2번째 까지를 B에서 A로 옮겨야 한다.

그래야 B에 있는 n - 1번째 원반을 C로 옮길 수 있다.

이 과정이 반복되는데 여기서 확인 할 수 있는 상황이 있다.

n번째 원반이 1ll << (n - 1) 번째에 원반으로 옮겨지기에 1ll << (n - 1)을 이용하여 옮겨지는 상황인지 그렇지 않은 상황인지 판단 후 처리를 해주면 된다.