문제 링크

😊 풀이

문제 난이도에 비해 한번 접해보지않으면 생각하기 힘들었다고 생각한다. 하나씩만 이동할수 있기때문에 분할정복-> 재귀로 풀어야했다.

다른 블로그의 풀이들을 참고했는데 죄다 같은 설명을 해놓아서 이해하는데 시간이걸렸다.
한줄씩 디버깅해가면서 혼자 이해해보려고했는데 전체적으로는 1->2로 하나씩 옮기고 1의 마지막 제일 큰 하나를 3으로 이동후 2에있는 나머지것들을 3으로 다시 쌓는다는것이다.

하지만 문제에서 항상 큰것이 아래로 가야하기때문에 우선 1을 2로 전부옮긴다기보다 3을 통해서 2로 놓는다고 생각하는게 더 낫다.

즉 코드에서 start는 시작점 end는 도착지이지만 mid를 통해 경유를 해야한다. 그렇지않으면 위쪽이 더 무거운게 쌓여버린다.

😊 코드

#include <iostream>
#include <cmath>
using namespace std;
void hanoi(int n, int start, int mid, int end) { 
	if (n == 1) cout << start << " " << end << '\n'; // 하나씩 끝까지 옮긴후 시작점 끝점 출력
	else {
		hanoi(n - 1, start, end, mid);//1. 1번기둥의 n-1개 -> 2번 기둥으로
		cout << start << " " << end << '\n'; //2. 2번기둥으로 끝까지옮긴후 나머지 제일 큰 것 1번기둥 -> 3번으로	
		hanoi(n - 1, mid, start, end);//3. 나머지 2번기둥(mid) -> 3번기둥(end)으로
	}
}//start: 출발점 mid : 하나씩놓기때문에 잠깐 지나는 경로 end : start,mid를 지나서 도착점
int main() {
	//원판의 개수
	int n;
	cin >> n;
	cout << (1 << n) - 1 << '\n';//2^n-1...pow()로 제곱하면 오답처리됨. 왜? pow()는 실수형으로 계산되기 때문..
	hanoi(n, 1, 2, 3);
	return 0;
}//총 가짓수는 2^n -1