[분할 정복] 하노이 탑 이동 순서

예제 입력 1

3

예제 출력 1

7

1 3

1 2

3 2

1 3

2 1

2 3

1 3

 

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

11729번: 하노이 탑 이동 순서

- 이동 횟수는 N개의 원판을 옮길 때, 각각 N-1번 N-1번으로 나누어지고 하나를 옮기게 되므로,

 

void solve(int n, int x, int y)
{
if (n == 0) return;
int z = 6 - x - y;

solve(n - 1, x, z); // N-1번
printf("%d %d\n", x, y);  // 1번
solve(n - 1, z, y);  // N-1번
}

 

D[N] = D[N-1] + D[N-1] + 1 = 2*D[N-1] + 1

 

#include <stdio.h>

int N;

int pow(int x, int n)
{
	int result = 1;

	for (int i = 0; i < n; i++) result *= x;

	return result;
}

void solve(int n, int x, int y)
{
	if (n == 0) return;
	int z = 6 - x - y;

	solve(n - 1, x, z);
	printf("%d %d\n", x, y);
	solve(n - 1, z, y);
}

int main(void)
{
	scanf("%d", &N);

	printf("%d\n", pow(2, N) - 1);
	solve(N, 1, 3);

	return 0;
}