백준_하노이 탑 이동 순서

[ 해결 방법 ]

원판이 몇 개가 있든 1번 장대에 원판이 2개가 있는 것처럼 생각하면 된다.

1번 장대에 원판이 2개 있다고 생각하면 처리 과정은 3단계이다.

1. 1 -> 2

2. 1 -> 3

3. 2 -> 3

원판이 n개 있을 때는 어떻게 진행할까?

제일 위에 원판 n-1개를 묶어서 움직이면 된다. 물론 그렇게 움직이면 안되지만 일단 가능하다고 생각을 해보자. 그러면 위의 경우처럼 3가지 밖에 안나온다. 

앞에서 n-1개의 원판을 2번 장대로 옮긴다고 했는데 어떻게 가능할까? 1번장대에서 n-2개의 원판을 3번 장대로 옮겨놓고 제일 아래 원판을 2번장대로 옮겨놓고 다시 3번장대의 n-2개를 2번으로 옮기면 된다. 이것도 3번만에 가능하다.

어떻게 해야할지 감이 오지 않나? 재귀적인 방법이 눈에 들어온다.

처음에 C++의 std::cout을 이용했을 땐 시간초과가 났다. 그런데, C의 printf로 돌리니 통과한다. 두 함수의 성능차이가 많이 나는 것같다.

[ 코드 ]

#include <stdio.h>
int N, Cnt;
int Process[2000000][2];
void DivConq(int n, int from, int to)
{
	int mid = 6 - from - to;
	
	if(n == 1)
	{
		Process[Cnt][0] = from;
		Process[Cnt++][1] = to;
	}
	else
	{
	  	DivConq(n - 1, from, mid);
	    // DivConq(1, from, to)를 불필요하게 호출할 필요없다.
		Process[Cnt][0] = from;		
	    Process[Cnt++][1] = to;
    	DivConq(n - 1, mid, to);  
	}
}
int main() {
	scanf("%d", &N);
	
	DivConq(N, 1, 3);
	
	printf("%d\n", Cnt);
	for(int i = 0; i < Cnt; i++)
		printf("%d %d\n", Process[i][0], Process[i][1]);
	return 0;
}