백준 11729 : 하노이의 탑

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

1. 접근

• 알고리즘에서 기본으로 많이 배우는 하노이의 탑
• 가장 아래의, n 원판을 옮기기 위해서는 n-1원판이 모두 3 장대가 아닌 다른 장대에 있어야 한다.
  => n-1 원판을 최종 원판이 아닌 다른 원판으로 옮긴다
• 최종 원판이 아닌 다른 원판은 어떻게 설정할까? => 시작, 끝 점 뿐만 아니라 가운데 지점을 인수로 활용한다.
• 특이하게 이 문제는 최종 이동 횟수를 출력 가장 상단에 나타내야 한다. => 2^n -1 라는 공식을 활용하여 미리 출력한다 (또는, 함수에서 바로 출력하지 않고 vector에 넣은 후, 이동 횟수를 출력한 후 벡터값들을 읽어오는 방법도 있다. 이 방법을 먼저 사용했으나 공식 사용하는게 더 적절해보여서 변경함)
• 간단한 하노이의 탑 흐름

1. n원판을 from에서 to로, middle을 거쳐 옮기고 싶다.
2. n-1까지의 원판을 from에서 middle로 옮겨놓는다.
3. n원판을 from에서 to로 옮긴다
4. middle로 옮겨놓은 n-1까지의 나머지 원판을 다시 to로 옮겨놓는다.
5. 이를 반복한다.

2. 나의 풀이

#include <iostream>
#include <cmath>
using namespace std;

int n;

void movePlateFromTo(int from,int middle, int to,int count) {
	
	if (count == 1) {
		cout << from << " " << to << "\n";
		return;
	}

	movePlateFromTo(from, to, middle, count -1); //흐름 2
	cout << from << " " << to << "\n"; //흐름 3
	movePlateFromTo(middle, from, to, count -1); //흐름 4

	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	cout << (int)pow(2, n) - 1 << "\n";
	movePlateFromTo(1, 2,3,n);

	return 0;
}

---

여담..

알고리즘 강의 들으면서 배웠던 기억을 살려가면서 풀었다..
n과 n-1 로 분리해서 푼다는 원리가 기억에 남아있어서 풀 수 있었다.
이게 기억에 남는게 진짜 신기하다 이래서 강의를 열심히 들어야하나보다