백준 11729_하노이 탑 이동 순서(C++)

 

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

11729번: 하노이 탑 이동 순서

[문제 풀이]

문제의 해결법은 재귀였던 것 같습니다.

하노이 타워를 푸는 일반적인 방법으로 문제를 풀었습니다.

N개의 원반을 시작 지점에서 끝 지점으로 옮기기 위해서는 가장 먼저 N크기의 원반을 1 -> 3의 지점 으로 먼저 옮겨야 합니다.

N크기의 원반이 1 -> 3의 지점으로 가기 위해서는 N-1개의 원반들이 2의 지점에 있어야 합니다.

다음 2의 지점에 있는 N-1크기의 원반을 3의 지점으로 보내기 위해서는 N-2개의 원반이 1의 지점으로 이동해야 합니다.

이것을 풀다 보면 한 개의 원반을 이동하는 문제로 축소됩니다.

이 방법을 재귀로 구현하였습니다.

 

이 코드의 핵심은

hanoi(n - 1, start, 6 - start - end);
printf("%d %d\n", start, end);
hanoi(n-1, 6 - start - end, end);

입니다.

 

원반을 옮기기 위해 걸린 횟수는 하노이 타워의 경우 

시간이 걸리므로 쉬프트 연산자 (1<<N) - 1을 이용하여 풀었습니다.

[코드]

#include<iostream>

using namespace std;

int N;

void hanoi(int n, int start, int end) {

	if (n <= 0)
		return;

	hanoi(n - 1, start, 6 - start - end);
	printf("%d %d\n", start, end);
	hanoi(n-1, 6 - start - end, end);

}

int main() {

	scanf("%d", &N);

	printf("%d\n", (1<<N) - 1);
	hanoi(N, 1, 3);
	

	return 0;

}