[백준 11729번/c++] 하노이 탑 이동 순서

알고리즘

 

재귀

 

---

문제 핵심

원판의 이동 과정

1. n개의 원판이 start에 쌓여있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 mid로 옮긴 다음,
2. 제일 밑에 있는 원판을 C로 옮긴다.
3. 이어서 mid에 있던 n-1개의 원판을 end로 옮긴다.

하노이탑의 최소이동횟수

• 2^n(하노이 탑의 원판 개수)-1이다.

 

---

전체 코드

#include <cstdio>
#include <cmath>

using namespace std;

void hanoi_tower(int n, int start, int mid, int end){
	if(n==1){
		printf("%d %d\n", start, end);
	} else{
		hanoi_tower(n-1, start, end, mid);
		printf("%d %d\n", start, end);
		hanoi_tower(n-1, mid, start, end);
	}
}

int main(){
	// freopen("input.txt", "rt", stdin);
    int n;
    scanf("%d", &n);
    printf("%d\n", (int)pow(2, n)-1);
    hanoi_tower(n, 1, 2, 3);
    
    return 0;
}