백준 1914 - 하노이 탑

문제 설명

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 하노이 탑의 이동 과정을 출력하면 된다.

단, N이 20이 넘는 경우에는 이동 횟수만 출력하면 된다.

 

우선, 이동 횟수를 구하는 방법은 간단하다.

하노이 탑의 이동 횟수는 $2^N - 1$이다.

하노이 탑의 원반을 옮기는 방법은 목표하는 기둥이 아닌 기둥에 N-1개를 옮긴 뒤 남은 1개의 원반을 목표 기둥으로 옮긴 뒤 다시 N-1개를 목표 기둥으로 옮기는 것이다.

N을 k+1이라고 표현한다면 다음과 같다.

$(2^k - 1) + 1 + (2^k - 1)$

이를 전개하여 정리한다면 $2^{k+1} - 1$이 된다.

k+1은 N이기 때문에 하노이 탑의 이동 횟수는 $2^N - 1$이 된다.

 

그럼 N이 20 이하일 때, 실제로 이동을 추적하는 함수는 다음과 같다.

void Move(int from, int to, int n)
{
	if (n == 1)
	{
		moves.push_back({ from, to });
		return;
	}

	int another = (1 + 2 + 3) - from - to;

	Move(from, another, n - 1);
	Move(from, to, 1);
	Move(another, to, n - 1);
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> moves;

void Move(int from, int to, int n)
{
	if (n == 1)
	{
		moves.push_back({ from, to });
		return;
	}

	int another = (1 + 2 + 3) - from - to;

	Move(from, another, n - 1);
	Move(from, to, 1);
	Move(another, to, n - 1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N;



	if (N <= 20)
	{
		Move(1, 3, N);

		cout << moves.size() << "\n";

		for (auto [from, to] : moves)
		{
			cout << from << " " << to << "\n";
		}
	}
	else
	{
		string str = to_string(pow(2, N));

		int a = str.find('.');
		str = str.substr(0, a);
		str[str.length() - 1] -= 1;

		cout << str << endl;
	}
	
	return 0;
}

---