×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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, - s - e);
    }
    else
    {
        arr[n - 1= e;
        hanoi(arr, n - 1, k - mid, - 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, 13);
 
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
 
    return 0;
}

Crocus



원리는 다음과 같다.


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)을 이용하여 옮겨지는 상황인지 그렇지 않은 상황인지 판단 후 처리를 해주면 된다.





반응형
  1. 잘 보고 갑니다~~