문제

풀이

• 하노이 탑 문제 풀이 (n : 원판)

1. 1번 장대에서 2번 장대로 : n-1개
2. 1번 장대에서 3번 장대로 : 1개 (제일 아래 큰 원판)
3. 2번 장대에서 3번 장대로 : n-1개
   -> 2^n-1 번 옮기면 원판을 최소 횟수로 옮길 수 있다.

• 원판 최대 개수 100개
  : 2를 100번 곱하면 매우 커지기 때문에 이동 횟수를 계산한 값을 문자열에 저장한다.

예시

• n = 1, K = 1
• n = 2, K = 3
• n = 3, K = 7
• n = 4, K = 15 ...

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

void hanoi(int n, int begin, int mid, int end) {
	if (1 == n) {
		cout << begin << " " << end << "\n";
		return;
	}
	hanoi(n - 1, begin, end, mid);
	cout << begin << " " << end << "\n";
	hanoi(n - 1, mid, begin, end);
}

int main() {
	int N;
	string str;
	cin >> N;

	// 이동 횟수 : 2^n-1
	str = to_string(pow(2, N));
str = str.substr(0, str.find('.'));
str.back()--;
	cout << str;
	if (20 >= N) {
		cout << "\n";
		hanoi(N, 1, 2, 3);
	}
	return 0;
}

---

참고
https://kimyunseok.tistory.com/60