알고리즘
[백준 11729번/c++] 하노이 탑 이동 순서
개발기록 :)
2022. 1. 17. 22:05
알고리즘
재귀
문제 핵심
원판의 이동 과정
- n개의 원판이 start에 쌓여있는 경우, 먼저 위에 쌓여 있는 n-1개의 원판을 mid로 옮긴 다음,
- 제일 밑에 있는 원판을 C로 옮긴다.
- 이어서 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;
}