백준 1914. 하노이 탑

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

1914번: 하노이 탑

 

하노이탑

 

우리의 목적은 n개의 원반을 1번 장대에서 3번 장대로 옮기는 것이다.

 

먼저 원반이 3개라고 생각해보자.

1 3, 제일 작은 원반을 1에서 3으로 옮긴다  

1 2, 두번째 원반을 1에서 2로 옮긴다 

3 2, 3에 있는 제일 작은 원반을 2로 옮긴다 

1 3, 가장 큰 원반을 3에 옮긴다 

2 1, 가장 작은 원반을 1로 옮긴다

2 3, 중간원반을 3으로 옮긴다 

1 3, 가장 작은 원반을 3으로 옮기고 끝낸다 

 

여기서의 규칙은 다음과 같다

가장큰 원반이 n이라면 

1.  가장 큰 원반 n을 제외한 n-1개의 원반을 1번장대 -> 2번장대

2. 가장 큰 원반 n번을 1번장대->3번장대

3. n-1개의 원반을 2번장대->3번장대 

 

처음에 3개의 원반을 예로들면

1번과정

1 3, 제일 작은 원반을 1에서 3으로 옮긴다 

1 2, 두번째 원반을 1에서 2로 옮긴다 

3 2, 3에 있는 제일 작은 원반을 2로 옮긴다 

 

2번과정

1 3, 가장 큰 원반을 3에 옮긴다 

 

3번과정

2 1, 가장 작은 원반을 1로 옮긴다

2 3, 중간원반을 3으로 옮긴다 

1 3, 가장 작은 원반을 3으로 옮기고 끝낸다 

 

즉 a장대에서 c장대로 옮길때 b장대를 중간이동으로 쓰는것.

 

 

큰 수 출력

하노이탑의 이동횟수는 2^n-1 번이다.

그런데 n은 100까지 이므로 string형태로 출력해야한다.

 

-1 을 뺄때를 어떻게 해야할지 햇갈렸는데 찾아보고 알았다.

2의 n승은 마지막 자리가 0이 될수 없으므로 그냥 빼주면된다고 한다.

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define endl '\n'


// a장대, b장대, c장대
void Hanoi(int n, int a, int b, int c)
{
    if(n == 1)
    {
        cout << a << ' ' << c << endl;
        return;
    }

    // 가장 큰 원반 n을 제외한 n-1개의 원반을 a에서 b로 옮기는데 경유지로 c를 사용한다
    Hanoi(n-1, a, c, b);

    cout << a << ' ' << c << endl;

    // 가장 큰 원반 n을 제외한 n-1개의 원반을 b에서 c로 옮기는데 경유지로 a를 사용한다
    Hanoi(n-1, b, a, c);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;

    // 하노이탑 이동횟수는 2^n-1
    string ans = to_string(pow(2,n));
    // 소수점 자리 인덱스 찾고
    int idx = ans.find('.');
    // 소수점 이하 제거
    ans = ans.substr(0, idx);
    // 2의 n승은 0으로 끝날수 없으므로 마지막자리는 그냥 1을 뺴주면됨 (이전 자리 건들여야할일 없음)
    ans[ans.length()-1] -= 1;
    cout << ans << endl;

    if(n <= 20)
        Hanoi(n, 1,2,3);


}