#11729 하노이 탑 이동 순서

# 문제

# 입력 및 출력

# 풀이
https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=2gumin14&logNo=221060149259 

하노이의 탑과 점화식

최소 이동횟수 점화식은 위의 블로그를 보면 잘 정리되어있음

 

하노이탑 원리는 아래 블로그를 보면 정확하게 이해됨

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

 

일단 하노이탑 원리를 정리하자면

1. N-1개의 원반을 B막대에 옮김

2. 맨 밑 원반을 C막대에 옮김

3. N-1개의 원반을 C막대에 옮김

 

1, 3은 재귀로 처리하면 되고, 2번은 원반 하나를 이동하는 것이기 때문에 재귀 호출은 필요 없음

 

#include <iostream>
#include <cmath>
using namespace std;

void hanoi(int n, int from, int by, int to)
{
	if (n == 1) cout << from << " " << to << "\n";
	else {
		hanoi(n - 1, from, to, by);
		cout << from << " " << to << "\n";
		hanoi(n - 1, by, from, to);
	}
}

int main() {
	int n;
	cin >> n;
	cout << pow(2, n) - 1 << "\n";
	hanoi(n, 1, 2, 3);
}

코드 자체는 문제 없는데 틀렸다고 떠서 당황했다ㅋㅋ

문제를 찾아보니까 pow가 문제였다

double형을 활용하기 때문에 숫자가 커질수록 오차가 발생해서 N에 20이 입력되면 틀렸다고 출력된다

그래서 시프트 연산을 활용했음

 

cout << (1 << n) - 1 << "\n";

시프트 연산의 원리는

여기서 1<<n은 1을 왼쪽으로 n번 시프트 하라는 의민데
0000 0001을 왼쪽으로 3번 시프트 하면 0000 1000이 된다

왼쪽 시프트는 *연산이 되고, 오른쪽 시프는 /연산이 됨

자세한 내용은 아래 블로그 참고

https://dojang.io/mod/page/view.php?id=174 

C 언어 코딩 도장: 23.3 시프트 연산자 사용하기

 

시프트 연산을 적용하면 아래 코드가 된다

#include <iostream>
#include <cmath>
using namespace std;

void hanoi(int n, int from, int by, int to)
{
	if (n == 1) cout << from << " " << to << "\n";
	else {
		hanoi(n - 1, from, to, by);
		cout << from << " " << to << "\n";
		hanoi(n - 1, by, from, to);
	}
}

int main() {
	int n;
	cin >> n;
	cout << (1 << n) - 1 << "\n";
	hanoi(n, 1, 2, 3);
}

하노이탑 문제는 재귀의 가장 기본적인 문제이기도 하고 변형문제로도 많이 나오니까 원리까지 제대로 알아봤음

 

나한텐 재귀가 넘 어려운 것 같다,,

재귀문제 많이 풀어봐야지