백준 1914번: 하노이탑

Se0ng_1l·2022년 7월 16일
0

백준

목록 보기
40/40

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

📌문제 접근

더러운 문제🤬
20까지는 재귀함수를 이용해 풀었고
21이상부터는 큰수연산으로 2^size로 문제를 풀었다.
재귀함수 작동 참고 영상: https://www.youtube.com/watch?v=Xu5GC_7YIeQ

많은 분들의 코드를 돌려 봤는데 대부분 출력초과 메모리초과가 발생했다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

queue<pair<int, int>> q;
void hanoi(int n, int from, int mid, int to)
{
    if(n == 1)
    {
        q.push(make_pair(from, to));
        return;
    }
    hanoi(n - 1, from, to, mid);
    q.push(make_pair(from, to));
    hanoi(n - 1, mid, from, to);
}

int main()
{
    int size;
    cin >> size;
    if(size <= 20){
        hanoi(size, 1, 2, 3);
        cout << q.size() << endl;
        while(!q.empty())
        {
            cout << q.front().first << " " << q.front().second << '\n';
            q.pop();
        }
    }
    else{
        vector<int> num;
        num.push_back(1);
        for(int i = 1; i <= size; i++)
        {
            int j = 0;
            int sum = 0;
            while(j < num.size())
            {
                int temp = sum + num[j] * 2;
                num[j] = temp % 10;
                sum = temp / 10;
                if(sum > 0)
                    num.push_back(0);
                j++;
            }
        }
        bool flag = false;
        num[0] -= 1;
        int len = num.size() - 1;
        while(len >= 0)
        {
            if(num[len] == 0 && !flag)
                len--;
            else if(num[len] != 0 && !flag)
            {
                flag = !flag;
                cout << num[len];
                len--;
            }
            if(flag)
            {
                cout << num[len--];
            }
        }
    }
}
profile
치타가 되고 싶은 취준생

0개의 댓글