백준 11729 하노이 탑 이동 순서

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

11729번: 하노이 탑 이동 순서

재귀 문제 예제로 정말 많이 쓰이는 문제이다. 설명을 할 때

 

start mid end 이런식으로 세부분으로 나누어서 설명하겠다. 

 

이 문제는 크게 네 분류로 나누어서 생각하면된다.

1. 최종적으로 옮겨야하는 마지막 한개를 제외하고 start에서 end를 거쳐 mid로 옮긴다. 
2. 마지막 남은 한개를 start에서 end부분 최종 목표로 옮긴다. 
3. 1번에서 옮긴 나머지 조각 들을 mid에서 start를 거쳐 다시 end로 옮긴다. 
4. 예외적으로 옮겨야할 조각이 1개 남았다면 start에서 end로 옮기면 된다. 

이 네 부분을 재귀코드로 잘 작성하면된다. 

example) start에 쌓인 조각이 3개일 때 

이 네 가지 규칙은 start에 조각이 4개든 5개든 6개든 상관없이 모두 적용이 되므로 아래와 같이 코드를 작성하면된다. 

 

#include <stdio.h>
#include <math.h>
void hanoi(int N, int start, int mid, int end);

int main(){
	int N;
	scanf("%d", &N);
	printf("%d\n", (int)pow(2,N)-1);
	hanoi(N, 1, 2, 3);
}	

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