기본적인 알고리즘인 하노이 탑을 구현하는 문제이다. 하노이 탑을 구현하는 것은 간단하게 할 수 있었지만 옮긴 횟수를 구할 때 신경을 써야한다. 문제에서 n
의 최댓값이 100이기 때문에 단순히 int
로 구한다면 실패를 하게된다. 문자열을 이용해서 옮긴 횟루를 구해주어야 한다. 어렵지 않게 풀 수 있었다.
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int N;
string result;
void hanoi(int start, int tmp, int end, int n) {
if (n == 1) {
cout << start << " " << end << "\n";
return;
}
hanoi(start, end, tmp, n - 1);
cout << start << " " << end << "\n";
hanoi(tmp, start, end, n - 1);
}
void solution() {
result = to_string(pow(2, N));
result = result.substr(0, result.find('.'));
result[result.size() - 1] -= 1;
cout << result << "\n";
if (N <= 20) {
hanoi(1, 2, 3, N);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
solution();
return 0;
}