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--];
}
}
}
}