[BOJ] 11729_하노이 탑 이동 순서 with cpp

# 생각

원판 n개를 a에서 b로 이동하는 함수를 만든다

void func(int a, int b, int n)

 

base condition은 n이 1일 때 a에서 b로 옮기는 것이다

if (n == 1)
	{
		cout << a << ' ' << b << '\n';
		return;
	}

 

나머지 재귀식은 아래처럼 작성할 수 있다

기둥이 1번, 2번, 3번 3개 이기때문에 기둥을 (1+2+3) - a - b로 표현 가능하다

	func(a, 6 - a - b, n - 1);		// n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다
	cout << a << ' ' << b << '\n';		// n번 원판을 기둥 a에서 기둥 b로 옮긴다
	func(6 - a - b, b, n - 1);		// n-1 개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다

 

 

# 전체 코드

(base condition을 0으로 줄 경우 더 간단하게 return으로 탈출만 해줘도 동일하게 동작한다)

#include <bits/stdc++.h>
using namespace std;

void func1(int a, int b, int n)
{
	if (n == 1)	// base condition
	{
		cout << a << ' ' << b << '\n';
		return;
	}
	func1(a, 6 - a - b, n - 1);		// n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
	cout << a << ' ' << b << '\n';		// n번 원판을 기둥 a에서 기둥 b로 옮긴다.
	func1(6 - a - b, b, n - 1);		// n-1 개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.
}

void func2(int a, int b, int n)
{
	if (n == 0)	// base condition
	{
		return;
	}
	func2(a, 6 - a - b, n - 1);		// n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
	cout << a << ' ' << b << '\n';		// n번 원판을 기둥 a에서 기둥 b로 옮긴다.
	func2(6 - a - b, b, n - 1);		// n-1 개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int k;
	cin >> k;
	//cout << (int)pow(2, k) - 1 << '\n';	// pow함수 사용시 double을 int로 형변환 해줘야 한다
	cout << (1 << k) - 1 << '\n';		// 1을 k칸 left shift = 2^k
	//func1(1, 3, k);
	func2(1, 3, k);
}

---

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

11729번: 하노이 탑 이동 순서