백준 1914번 하노이 탑

문제 링크입니다: https://www.acmicpc.net/problem/1914

하노이 탑은 재귀적으로 접근한다면 꽤 쉽게 풀 수 있는 문제입니다.

알고리즘은 아래와 같습니다.(우선, N=3일 때를 설명하겠습니다)

1. a, b, c 기둥이 있고 처음에 원판들은 모두 a에 있습니다.

2. 첫 번째 원판을 c로 옮깁니다.(현재 상태: (2, 3), 0, (1))

3. 두 번째 원판을 b로 옮깁니다.(현재 상태: (3), (2), (1))

4. 첫 번째 원판을 b로 옮깁니다.(현재 상태: (3), (1, 2), 0)

5. 세 번째 원판을 c로 옮깁니다.(현재 상태: 0, (1, 2), (3))

6. 첫 번째 원판을 a로 옮깁니다.(현재 상태: (1), (2), (3))

7. 두 번째 원판을 c로 옮깁니다.(현재 상태: (1), 0, (2, 3))

8. 마지막으로 첫 번째 원판을 c로 옮깁니다.(현재 상태: 0, 0, (1, 2, 3))

여기서 찾을 수 있는 규칙은 아래와 같습니다.

1. 제일 큰 원반을 제외한 N-1개의 원반들을 A 기둥에서 B 기둥으로 이동시킵니다.

2. 제일 큰 원반 한개를 A 기둥에서 C 기둥으로 이동시킵니다.

3. 1번에서 옮겨진 원반들을 B기둥에서 C 기둥으로 이동시킵니다.

그리고, N > 20부터는 원반들이 옮겨지는 횟수만 구하면 되는데 결국 (2^N - 1)을 출력해주면 되는 문제였습니다.

하지만 2^100은 long long 자료형으로도 표현할 수 없기 때문에 string을 통해 Big Integer를 구현해줘야했습니다.

따라서, bigNumAdd 함수를 통해 2^N을 표현하였고 subtractOne 함수를 통해 1을 빼줬습니다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

 

int N;

long long cnt;

vector<pair<int, int>> v;

 

string bigNumAdd(string num1, string num2)

{

        long long sum = 0;

        string result;

 

        //1의 자리부터 더하기 시작한다

        while (!num1.empty() || !num2.empty() || sum)

        {

                 if (!num1.empty())

                 {

                         sum += num1.back() - '0';

                         num1.pop_back();

                 }

                 if (!num2.empty())

                 {

                         sum += num2.back() - '0';

                         num2.pop_back();

                 }

                 //다시 string 형태로 만들어 push_back

                 result.push_back((sum % 10) + '0');

                 sum /= 10;

        }

        //1의 자리부터 result에 넣었으므로 뒤집어줘야한다

        reverse(result.begin(), result.end());

        return result;

}

 

//2의 n승은 0으로 끝날 수 없으므로

string subtractOne(string num)

{

        vector<int> v;

        int back = num.back() - '0';

        num.pop_back();

        back -= 1;

        num.push_back(back + '0');

 

        return num;

}

 

void Hanoi(int num, int from, int by, int to)

{

        if (num == 1)

                 v.push_back({ from, to });

        else

        {

                 Hanoi(num - 1, from, to, by);

                 v.push_back({ from, to });

                 Hanoi(num - 1, by, from, to);

        }

}

 

int main(void)

{

        cin >> N;

 

        if (N <= 20)

        {

                 Hanoi(N, 1, 2, 3);

                 cout << v.size() << "\n";

                 for (int i = 0; i < v.size(); i++)

                         cout << v[i].first << " " << v[i].second << "\n";

        }

        else

        {

                 string num = "2";

                 for (int i = 0; i < N - 1; i++)

                 {

                         string temp = bigNumAdd(num, num);

                         num = temp;

                 }

                 cout << subtractOne(num) << "\n";

        }

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~